String Compression

Q: What is the time complexity of String Compression?

The two-pointer walk takes O(n) time, because the scanning index only moves forward. Apart from the result it keeps two indexes, so the extra space is O(1) .

EasyTwo pointers Arrays and strings

+10

You get a string s of English letters. Compress it: replace every run of two or more equal letters in a row with that letter followed by the length of the run, and leave a letter that stands alone as it is. So aabccc becomes a2bc3. Return the compressed string.

Upper and lower case are different letters: aA is two runs of length 1.

Function

compress(s: string) → string

sstring: the string to compress, English letters only
Returnsstring: the compressed string, each run written as its letter plus its length when the length is more than 1

Constraints

1 ≤ s.length ≤ 2 × 10⁴
s contains only English letters, a to z and A to Z.
A run length is written in decimal and can have several digits.

Examples

Input: s = "aabccc"
Output: "a2bc3"
Explanation: The runs are aa, b and ccc. They become a2, b (a lone letter gets no count) and c3.

Input: s = "abbbbbbbbbbbb"
Output: "ab12"
Explanation: One a, then twelve bs. The length 12 is written as the two characters 1 and 2, so the result is ab12.

Input: s = "zzZZZ"
Output: "z2Z3"
Explanation: Lower case z and upper case Z are different letters, so this is a run of two followed by a run of three: z2Z3.

Follow-up

Write the reverse: given a compressed string such as ab12, rebuild the original. How do you read a count that has several digits?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

Find where each run of equal letters starts and ends, then write its length as text. A run of one letter gets no count, and a count can have several digits. Two indexes, one at the start of a run and one scanning to its end, do it in one pass.

Collect the runs, then write them

Intuition

First record the runs as pairs of a letter and a length: for aabccc, (a, 2), (b, 1), (c, 3). Each letter either extends the last run or opens a new one. Then write each run's letter, followed by its length when it is more than 1.

Both passes are O(n). The list can hold n runs when no two neighbours match, so it costs O(n) extra space.

Algorithm

Create an empty list of runs.
For each letter of s: if the last run has the same letter, add 1 to its length; otherwise append a new run of length 1.
For each run, write its letter, then its length as decimal text if the length is more than 1.

def compress(s):
    # First pass: collect the runs as [letter, length] pairs
    runs = []
    for ch in s:
        if runs and runs[-1][0] == ch:
            runs[-1][1] += 1
        else:
            runs.append([ch, 1])
    # Second pass: write each run, with its length when it is more than 1
    parts = []
    for letter, length in runs:
        parts.append(letter)
        if length > 1:
            parts.append(str(length))
    return "".join(parts)

Two pointers over each run

Intuition

Keep i at the first letter of the current run and move j forward while s[j] equals s[i]. When j stops, at a different letter or at the end, the run's length is j-i. Write it and set i = j. On abbbbbbbbbbbb, j first stops at 1, giving a, then at 13, giving b12.

The last run needs no special case, because the inner loop stops at the end of the string. j only moves forward, so the time is O(n), and besides the result you keep two indexes. The R and Swift versions split s into a character array first, so they use O(n) extra space.

Algorithm

Set i = 0.
While i is inside the string, set j = i and move j forward while it is inside the string and s[j] equals s[i].
Write s[i]; if j-i is more than 1, write it as decimal text.
Set i = j and repeat.

def compress(s):
    parts = []
    n = len(s)
    i = 0
    while i < n:
        # Move j to the first index after the run that starts at i
        j = i
        while j < n and s[j] == s[i]:
            j += 1
        parts.append(s[i])
        if j - i > 1:
            parts.append(str(j - i))
        i = j
    return "".join(parts)

Pitfalls and edge cases

Writing a run only when you meet a different letter. Nothing follows the final ccc of aabccc, so you return a2b.
Writing the count as one character, such as '0' + count. It breaks at 10: twelve bs need the two characters 12.
Writing 1 after a lone letter. b stays b, not b1.
Ignoring case. zzZZZ is z2Z3, not z5.
Growing an immutable string with +, as in Java or C#. Each + copies the result so far, which makes the loop O(n²); use a string builder.

Frequently asked questions3

What is the time complexity of String Compression?

The two-pointer walk takes O(n) time, because the scanning index only moves forward. Apart from the result it keeps two indexes, so the extra space is O(1).

Can the compressed string be longer than the original?

Not in this version. A lone letter stays one character, and a run of k ≥ 2 letters becomes one letter plus the digits of k, never more than k characters. A scheme that writes a count after every letter, such as a1b1, can double the length.

How do you compress a string in place?

Use a character array with a read index and a write index. Scan each run with the read index, then write its letter and the digits of its length at the write index. The output is never longer than the input read so far, so the write index never overtakes the read index. Return the new length at the end.