DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

String Compression

mediumStrings

Problem statement

You are given an array of characters chars. Compress it in place: for each run of equal consecutive characters, write the character once, followed by the run length if the run is longer than 1. A run length of 10 or more is written as separate digit characters (12 becomes '1', '2').

Write the result into the start of chars and return its new length. Characters after that length don't matter. The goal is to use only constant extra space.

Examples

Example 1

Input: chars = ["x","x","x","y","z","z"]

Output: 5, chars starts with ["x","3","y","z","2"]

Explanation: The runs are xxx, y and zz. The single y gets no count.

Example 2

Input: chars = ["q","w","w","w","w","w","w","w","w","w","w","w","w"]

Output: 4, chars starts with ["q","w","1","2"]

Explanation: Twelve w characters become "w" followed by the digits 1 and 2.

Hints

Approach

Use two pointers on the same array: read finds runs, write stores the compressed output.

  1. While read < n: remember ch = chars[read] and start = read, then advance read past the run.
  2. Write ch at write and advance write.
  3. If the run length read - start is more than 1, write each of its digits and advance write for each.
  4. Return write.

This is safe because a run of length r is replaced by at most r characters (1 character plus fewer digits than the run length when r >= 2). So write never overtakes read and never overwrites anything still unread.

ComplexityTime O(n)Space O(1)
Python
class Solution:
def compress(self, chars: list[str]) -> int:
n = len(chars)
read = write = 0
while read < n:
ch, start = chars[read], read
while read < n and chars[read] == ch:
read += 1 # skip to the end of the run
chars[write] = ch
write += 1
if read - start > 1:
for d in str(read - start): # one slot per digit
chars[write] = d
write += 1
return write

Follow-up questions

  • Write the matching decompress function.
  • Only compress when it actually makes the output shorter, and otherwise leave the array unchanged.

Frequently asked questions

No. A count has at most as many digits as n itself (about 4 for 1,000 characters), so it is conventionally treated as constant space.

Each run shrinks or stays the same length when compressed, so the write position is always at or behind the read position. Nothing is overwritten before it has been read.

Collapsing repeated items is common in operations tooling: turning thousands of identical log lines into message (x1200), or summarising a health-check history like OK x45, FAIL x3. The in-place, two-pointer version tests whether you can reason about buffers without extra memory.