String Compression

Difficulty: Medium

Problem

Shrink the character array chars in place using run-length encoding. Walk through chars from left to right; for each maximal run of the same character, write that character, and also write the run's length if the run is longer than one. Lengths of 10 or more are written one digit per array slot. The result must be stored inside chars itself rather than in a separate string. When done, return the number of slots of chars that the encoding uses.

Example

Input: chars = ["x","x","x","y","z","z"]
Output: 5, chars = ["x","3","y","z","2"]
Explanation: The runs are "xxx", "y", "zz", which encode to "x3yz2" (a lone "y" gets no count). The first 5 slots of chars hold this, so return 5.

Brute-force approach

Build a new compressed string first, then copy it back into the original array. Uses extra O(n) space for the intermediate string.

Steps

  1. Iterate through chars counting consecutive groups
  2. Build a new compressed list with chars and counts
  3. Copy the compressed list back into the original array
  4. Return the new length

Time complexity: O(n) · Space complexity: O(n)

Trade-offs

  • Uses O(n) extra space for the compressed list
  • Requires a copy-back step
  • Not truly in-place: the problem asks for in-place modification

Optimal approach

Key insight: The write pointer always lags behind (or equals) the read pointer, so we can safely overwrite without losing unread data.

Use two pointers: a read pointer to scan groups and a write pointer to overwrite the array from the front. Since compressed output is always ≤ original length, the write pointer never overtakes the read pointer.

Steps

  1. Initialize read = 0, write = 0
  2. While read < len: count group of identical chars
  3. Write the character at write position
  4. If count > 1, write each digit of the count
  5. Return write as the new length

Time complexity: O(n) · Space complexity: O(1)

Pseudocode

function compress(chars):
    write = 0
    read = 0
    while read < len(chars):
        char = chars[read]
        count = 0
        while read < len(chars) and chars[read] == char:
            read++
            count++
        chars[write] = char
        write++
        if count > 1:
            for digit in str(count):
                chars[write] = digit
                write++
    return write

Hints

  • Use read and write pointers. Read scans forward, write overwrites from the front
  • Count consecutive characters, then write the char and its count
  • For counts >= 10, write each digit separately

Complexity questions

What is the time complexity of the in-place two-pointer compression?

O(n). The read pointer visits each character exactly once → O(n).

What is the space complexity of the in-place approach?

O(1). Only read, write, count, and char variables, constant extra space.

Why can we safely overwrite chars in-place without losing data?

Because the compressed form is always shorter than or equal to the original. The write pointer never passes the read pointer because compression never expands the data.

Check your understanding of String Compression

Given chars = ['a','b','c'], what is the compressed result?

['a','b','c']: length 3. Each character appears once, so no count is written. The array stays ['a','b','c'] with length 3.

How is a count of 12 stored in the chars array?

As two elements: '1' and '2'. The count 12 is split into individual digits: '1' then '2'.

Must the compression be done in-place (modifying the original array)?

Yes, modify chars in-place and return the new length. Overwrite the original array and return the new length. The compressed result is always ≤ original length.

Why is the compressed length always ≤ the original length?

Because groups of length 1 use 1 slot (same as before) and groups of length ≥ 2 use at most the same or fewer slots. A group of 2 identical chars takes 2 slots (char + '2') = same size. Groups ≥ 3 always shrink. So compressed ≤ original.

Related problems

Keep practising