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.
public int compress(char[] chars) {
int anchor = 0, write = 0;
for (int read = 0;
read < chars.length;
read++) {
if (read + 1 == chars.length || chars[read + 1] != chars[read]) {
chars[write++] = chars[anchor];
if (read > anchor) {
for (char c : ("" + (read - anchor + 1)).toCharArray()) {
chars[write++] = c;
}
}
anchor = read + 1;
}
}
return write;
}Follow-up:
How would you modify the solution to handle uppercase letters and digits?
