String Compression
Given an array of characters, replace repeated characters with the character and the count of consecutive occurrences of the character in the array.
Constraints:
- 1 <= chars.length <= 100
- chars[i] is a lowercase English letter
Examples:
Input: ["a","a","b","b","c","c","c"]
Output: ["a","2","b","2","c","3"]
Explanation: Replace repeated characters with the character and the count of consecutive occurrences of the character in the array.
Solutions
Two Pointers
Time: O(n)Space: O(n)
Use two pointers, anchor and write, to track the start of the current sequence and the position to write the compressed sequence. Iterate through the array, and when a different character is encountered, write the character and the count of consecutive occurrences to the array.
def compress(chars):
anchor = write = 0
for read in range(len(chars)):
if read + 1 == len(chars) or chars[read + 1] != chars[read]:
chars[write] = chars[anchor]
write += 1
if read > anchor:
for c in str(read - anchor + 1):
chars[write] = c
write += 1
anchor = read + 1
return writeFollow-up:
How would you modify the solution to handle uppercase letters and digits?
