Compress a String Using Run-Length Encoding

Given a string s, compress it using run-length encoding: every run of consecutive identical characters becomes that character followed by the run's length, unless the run has length 1, in which case just the character is written with no count. Building the compressed result by repeatedly concatenating onto a plain string works, but in most languages a string is immutable — every += allocates a brand new string and copies everything built so far into it, turning n appends into O(n²) work. Appending to a mutable builder instead (a StringBuilder, a list joined at the end, or a pre-sized buffer) keeps each append O(1) amortized, bringing the whole pass down to O(n).

Test Case 1:

Input:s = "aaabbc"

Output:"a3b2c"

Explanation:The run of 3 a's becomes a3, the run of 2 b's becomes b2, and the single c stays just c.

Test Case 2:

Input:s = "abc"

Output:"abc"

Explanation:Every run has length 1, so no counts are ever appended — the output equals the input.

Test Case 3:

Input:s = "aabbcc"

Output:"a2b2c2"

Explanation:Three runs of length 2 each.

Constraints

◆1 ≤ s.length ≤ 2000
◆s consists only of lowercase English letters

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

🧪Try your own test case

s (lowercase string) — 3-12 lowercase letters

1	class Solution {
2	public String compressString(String s) {
3	StringBuilder result = new StringBuilder();
4	int i = 0;
5	while (i < s.length()) {
6	char c = s.charAt(i);
7	int count = 0;
8	while (i < s.length() && s.charAt(i) == c) {
9	count++;
10	i++;
11	}
12	result.append(c);
13	if (count > 1) result.append(count);
14	}
15	return result.toString();
16	}
17	}
18

a

b

c

Variables

result

i0

INITIALIZE

Start with an empty (mutable) result builder and i at 0 — appending to it never rebuilds the whole string from scratch.

Step 1 / 11

Approach & Solutions

Brute Force — Repeated Concatenation

Brute

Walk through the string counting each run of repeated characters, and build the result by repeatedly concatenating onto a plain string with +=. Correct, but in languages with immutable strings every += copies everything built so far, making the whole pass O(n²) instead of O(n).

TimeO(n²)

SpaceO(n)

Java

Try it out

class Solution {
    public String compressString(String s) {
        String result = "";
        int i = 0;
        while (i < s.length()) {
            char c = s.charAt(i);
            int count = 0;
            while (i < s.length() && s.charAt(i) == c) {
                count++;
                i++;
            }
            result += c;
            if (count > 1) result += count;
        }
        return result;
    }
}

Optimal — StringBuilder

Optimal

Identical run-counting logic, but append to a mutable builder (StringBuilder in Java, a list joined at the end in Python, a reserved std::string in C++, a pre-sized buffer in C) instead of rebuilding an immutable string on every append. Each append becomes O(1) amortized, so the whole pass is O(n).

TimeO(n)