String Compression
Medium · Two Pointers · Two Pointers · String
Problem
You are given an array of characters chars. Compress it in place: for each maximal run of the same character, write the character once, and if the run is longer than 1, follow it with the run length written as separate digit characters (a run of 12 becomes "1", "2").
Return the new length k. The compressed characters must occupy chars[0:k]; whatever is left after them is ignored. Use only constant extra space.
The tests check both k and chars[0:k].
Examples
Input: chars = ["x","x","y","z","z","z"] Output: 5, chars = ["x","2","y","z","3"]
The runs xx, y and zzz become "x2", "y" and "z3".
Input: chars = ["k"] Output: 1, chars = ["k"]
A single character is left as it is.
Input: chars = ["a","b","b","b","b","b","b","b","b","b","b","b","b"] Output: 4, chars = ["a","b","1","2"]
The twelve bs become "b", "1", "2".
Constraints
- 1 <= len(chars) <= 2000
- chars[i] is a lowercase or uppercase English letter, a digit, or a symbol
Approaches
- Baseline: build the result separately, then copy it back — time O(n), space O(n)
Follow-up
How would you undo it? Read a character, then all the digits after it, and write the run back out: see the use case “Expand a compressed string”. If compression should only be kept when it saves space, compare lengths and stop early once it cannot.
Related problems
Start free on Cariara · Coding problems · System design studio
