Rosetta Stone Challenge: Run-Length Encoding v2.0 The goal of a Rosetta Stone Challenge is to write solutions in as many languages as possible. Show off your programming multilingualism!

The Challenge

We've done run-length encoding before but only considered runs of a single character. Of course, we can sometimes make even greater savings if we consider runs of multiple characters.

Take aaaxyzxyzxyzdddd for instance. This can be compressed to 3a3{xyz}4d. Your task is to write a program of function which, given a case-sensitive string of letters and spaces, compresses it optimally using run-length encoding for multi-character runs.

You may take input via function argument, STDIN or ARGV and return the result or print it to STDOUT.

Runs must not be nested, so aaabbbaaabbb must be 3a3b3a3b, not 2{3a3b}. I.e. the string should be encoded (or decoded) in a single pass.

Consequences of Optimal Compression

Some examples where naive application of run-length encoding might lead to suboptimal results:


abab must not be "compressed" to 2{ab}
aaaabcdeabcde must not be compressed to 4abcdeabcde but 3a2{abcde} instead.


If there are two optimal versions (e.g. aa and 2a or abcabc and 2{abc}) either result is fine.

Examples

Input              Output

aa                 aa -or- 2a
aaaaaAAAAA         5a5A
ababa              ababa
abababa            a3{ba} -or- 3{ab}a
foo foo bar        2{foo }bar
aaaabcdeabcde      3a2{abcde}
xYzxYz             xYzxYz -or- 2{xYz}
abcabcdefcdef      abcab2{cdef}
pppqqqpppqqq       3p3q3p3q
pppqqqpppqqqpppqqq 3{pppqqq}


Scoring

Each language is a separate competition as to who can write the shortest entry, but the overall winner would be the person who wins the most of these sub-competitions. This means that a person who answers in many uncommon languages can gain an advantage. Code golf is mostly a tiebreaker for when there is more than one solution in a language: the person with the shortest program gets credit for that language.

If there is a tie, the winner would be the person with the most second-place submissions (and so on).

Rules, Restrictions, and Notes

Please keep all of your different submissions contained within a single answer.

Also, no shenanigans with basically the same answer in slightly different language dialects. I will be the judge as to what submissions are different enough.

Current Leaderboard

This section will be periodically updated to show the number of languages and who is leading in each.


C# (265) — edc65
JavaScript (206) — edc65
Python (214) — Will
VB.NET (346) — edc65


Current User Rankings


edc65 (3)
Will (1)
Python 214

def t(s):
 b=s;l=len;r=range(1,l(s))
 for i in r:
  p=s[:i];b=min(b,p+t(s[i:]),key=l);x=1
  for j in r:k=i*j+i;x*=p==s[i*j:k];b=min(b,(b,''.join((`j+1`,"{"[i&lt;2:],p,"}"[i&lt;2:],t(s[k:]))))[x],key=l)           
 return b


(second level indent is tab)

As this is code-golf, this is the naive recursive approach without early-exit, so its really really slow.