String Compression

Medium· two pointers· run-length encoding

Problem

Compress a character array in place: each group of consecutive repeated characters becomes the character followed by its count, and groups of length one are written as just the character. Counts of 10 or more take several array cells. Return the new length of the array.

Examples

Input: chars = ["a","a","b","b","b","c","c","c","c"]

Output: 6, chars starts with ["a","2","b","3","c","4"]

Input: chars = ["a","b","b","b","b","b","b","b","b","b","b","b","b"]

Output: 4, chars starts with ["a","b","1","2"]

The run of twelve b characters is written as "b", "1", "2".

Constraints

• 1 <= chars.length <= 2000
• chars[i] is a letter, digit or symbol
• Use O(1) extra space

Hints & approach

Hint 1

Use one pointer to read groups and another to write the compressed output.

Hint 2

The write pointer never overtakes the read pointer, so overwriting is safe.

Approachtry the hints first

Keep a read index and a write index. At each step, find the end of the current run starting at read. Write the run's character at write, and if the run is longer than one, write each digit of its length after it. Move read to the end of the run and repeat. The compressed form is never longer than the original, so writing behind the reader never destroys unread data; return write at the end.

Time O(n) · Space O(1)

← PreviousZigzag Conversion Next →Shortest Palindrome