Coding problem · Easy · Basics

Run-Length Encoding

Easy Algorithms & data structures

Compress s with run-length encoding: each group of consecutive identical characters becomes the character followed by how many times it repeats.

"aaabccdddd" becomes "a3b1c2d4".

Example 1

Input: s = "aaabccdddd"
Output: "a3b1c2d4"

Example 2

Input: s = "abc"
Output: "a1b1c1"

Hints

Hint 1

Walk through the string while counting how long the current run is.

Hint 2

When the character changes (or the string ends), write the character and its count, then start a new run.

Write and run your solution

Loading the editor… (JavaScript is required to run code in your browser.)

Solution and explanation

Show the solution

Time O(n) · Space O(n)

Keep the current character and a counter. Each time the next character differs, append char + count and reset. Don't forget to write the last run after the loop.

Reference solution

function runLengthEncode(s) {
  let out = '';
  for (let i = 0; i < s.length; ) {
    let j = i;
    while (j < s.length && s[j] === s[i]) j++;
    out += s[i] + (j - i);
    i = j;
  }
  return out;
}

function runLengthEncode(s: string): string {
  let out = '';
  for (let i = 0; i < s.length; ) {
    let j = i;
    while (j < s.length && s[j] === s[i]) j++;
    out += s[i] + (j - i);
    i = j;
  }
  return out;
}

def run_length_encode(s: str) -> str:
    out = []
    i = 0
    while i < len(s):
        j = i
        while j < len(s) and s[j] == s[i]:
            j += 1
        out.append(f'{s[i]}{j - i}')
        i = j
    return ''.join(out)

<?php

function runLengthEncode(string $s): string
{
    $out = '';
    $n = strlen($s);
    for ($i = 0; $i < $n; ) {
        $j = $i;
        while ($j < $n && $s[$j] === $s[$i]) {
            $j++;
        }
        $out .= $s[$i] . ($j - $i);
        $i = $j;
    }
    return $out;
}

class Solution {
    public String runLengthEncode(String s) {
        StringBuilder out = new StringBuilder();
        for (int i = 0; i < s.length(); ) {
            int j = i;
            while (j < s.length() && s.charAt(j) == s.charAt(i)) j++;
            out.append(s.charAt(i)).append(j - i);
            i = j;
        }
        return out.toString();
    }
}

Was this page helpful?