359. String Compression
You receive chars, an array of characters. Compress it in place using run-length encoding: walk the array as a sequence of runs (maximal stretches of one repeated character) and rewrite each run as the character itself, followed by the run's length — but only append the length when the run is longer than 1. A length of 10 or more is written out digit by digit (a run of 12 bs becomes b, 1, 2 — three separate array slots).
Your function returns the compressed length k; after it runs, the first k slots of chars must hold the compressed sequence. Whatever sits past index k − 1 is ignored.
Do it with constant extra memory — that in-place requirement is the whole interview.
Example 1:
Input: chars = ["a","a","b","b","c","c","c"]
Output: 6, with chars[0..5] = ["a","2","b","2","c","3"]
Explanation: Three runs: "aa" → a2, "bb" → b2, "ccc" → c3. The first 6 slots become ["a","2","b","2","c","3"] and the function returns 6.
Example 2:
Input: chars = ["a"]
Output: 1, with chars[0..0] = ["a"]
Explanation: A run of length 1 keeps just its character — no count is written.
Example 3:
Input: chars = ["a","b","b","b","b","b","b","b","b","b","b","b","b"]
Output: 4, with chars[0..3] = ["a","b","1","2"]
Explanation: The single "a" stays bare; the 12 "b"s compress to b followed by the digits 1 and 2.
Constraints:
- 1 ≤ chars.length ≤ 2000
- chars[i] is a lowercase English letter, an uppercase English letter, or a digit.
- Comparisons are case-sensitive: "a" and "A" are different characters.
Hints:
First solve it without the memory limit: scan run by run, build the encoding in a fresh list, then copy it back. That shape — find the end of the current run, emit char + count — is the whole algorithm.
For the in-place version keep two indices: read (where the current run starts) and write (where the next output character lands). Why can write never overtake read?
A run of length r ≥ 2 encodes into 1 + digits(r) ≤ r slots, and a run of length 1 into exactly 1 — so the output prefix never outgrows the input you have already consumed.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: chars = ["a","a","b","b","c","c","c"]
Expected output: 6, chars = ["a","2","b","2","c","3", ...]