Run-length string compression

Medium TimeO(n) SpaceO(n)

Given a string s, return it with each run of identical consecutive characters replaced by that character followed by the length of the run, so "aaabccddddd" becomes "a3b1c2d5". A run of one still carries its count, so "b" becomes "b1". Only consecutive characters form a run. Because this can make a string longer, the original is returned whenever the encoded form is not shorter.

Examples

Example 1

Input
s = "aaabccddddd"
Output
"a3b1c2d5"
Runs of 3, 1, 2 and 5 become a3, b1, c2 and d5 — 8 characters against the 11 they replace.

Example 2

Input
s = "abc"
Output
"abc"
Three runs of one encode to "a1b1c1", which is longer than "abc", so the original is returned.

The Code

function compress(s) {
  let out = "";
  let i = 0;
  while (i < s.length) {
    const ch = s[i];
    let run = 0;
    while (i < s.length && s[i] === ch) {
      run++;
      i++;
    }
    out += ch + run;
  }
  return out.length < s.length ? out : s;
}
compress("aaabccddddd");
Done

The first 19 calls, of 21. This one does not fit on a page.

Step through compress("aaabccddddd") call by call

More like this

All strings examples (13) →