Problem statement

Compress a string using run-length encoding: replace each maximal run of a repeated character by that character followed by the run length. A run of length 1 is written as the character alone, with no number.

Return the compressed string.

Example 1

Input: chars = "aabbccc"
Output: a2b2c3

Example 2

Input: chars = "a"
Output: a
Explanation: A run of one keeps no count.

Example 3

Input: chars = "abbbbbbbbbbbb"
Output: ab12
Explanation: Multi-digit counts are written out in full.

Constraints

• 1 <= chars.length <= 40
• chars consists of lowercase English letters.

Follow-up: The interview version modifies the character array in place and returns the new length, using O(1) extra space.

Hints for String Compression

1. Hint 1

   Walk the string with a run-start index and a scanning index.

2. Hint 2

   Append the character, and append the count only when the run is longer than one.

3. Hint 3

   Counts of ten or more contribute several characters — write the whole number, not one digit.

How to solve String Compression

Scan runs of identical characters; emit the character, then its length only when the run exceeds one.

Approach

1. With i at the run start, advance j while chars[j] == chars[i].
2. Append chars[i]; if j - i > 1, append the decimal digits of j - i.
3. Set i = j and repeat.

Why it works

Maximal runs partition the string, and the rules specify exactly the character-plus-count representation with the count omitted for singletons.

Complexity

• Time — O(n)
• Space — O(n) for the output

Pitfalls

• A count of 10 or more contributes multiple characters — write the full number.
• The in-place array version writes with a separate write pointer and returns the new length.

Reference solution

Python

def compress(chars: str) -> str:
    out = []
    i = 0
    while i < len(chars):
        j = i
        while j < len(chars) and chars[j] == chars[i]:
            j += 1
        out.append(chars[i])
        if j - i > 1:
            out.append(str(j - i))
        i = j
    return "".join(out)

Java

public static String compress(String chars) {
    StringBuilder out = new StringBuilder();
    int i = 0;
    while (i < chars.length()) {
        int j = i;
        while (j < chars.length() && chars.charAt(j) == chars.charAt(i)) j++;
        out.append(chars.charAt(i));
        if (j - i > 1) out.append(j - i);
        i = j;
    }
    return out.toString();
}

C++

string compress(string chars) {
    string out = "";
    int i = 0;
    int n = (int) chars.size();
    while (i < n) {
        int j = i;
        while (j < n && chars[j] == chars[i]) j++;
        out += chars[i];
        if (j - i > 1) out += to_string(j - i);
        i = j;
    }
    return out;
}

JavaScript

var compress = function(chars) {
    let out = "";
    let i = 0;
    while (i < chars.length) {
        let j = i;
        while (j < chars.length && chars[j] === chars[i]) j++;
        out += chars[i];
        if (j - i > 1) out += String(j - i);
        i = j;
    }
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Merge Two Sorted Linked Lists in Reverse Order Medium
• Rotate a Linked List Medium
• Segregate Even and Odd Nodes in a Linked List Medium
• Maximum Twin Sum of a Linked List Medium
• Delete the Middle Node of a Linked List Medium
• Swapping Nodes in a Linked List Medium