The length after compression must always be smaller than or equal to the original array.
Every element of the array should be a character (not int) of length 1.
After you are done modifying the input array in-place, return the new length of the array.
Follow up:
Could you solve it using only O(1) extra space?
Example 1:
Input:
["a","a","b","b","c","c","c"]
Output:
Return 6, and the first 6 characters of the input array should be: ["a","2","b","2","c","3"]
Explanation:
"aa" is replaced by "a2". "bb" is replaced by "b2". "ccc" is replaced by "c3".
Example 2:
Input:
["a"]
Output:
Return 1, and the first 1 characters of the input array should be: ["a"]
Explanation:
Nothing is replaced.
Example 3:
Input:
["a","b","b","b","b","b","b","b","b","b","b","b","b"]
Output:
Return 4, and the first 4 characters of the input array should be: ["a","b","1","2"].
Explanation:
Since the character "a" does not repeat, it is not compressed. "bbbbbbbbbbbb" is replaced by "b12".
Notice each digit has it's own entry in the array.
Note:
1. All characters have an ASCII value in [35, 126].
2. 1 <= len(chars) <= 1000.
Solution:
This problem is similar to count and say.
We iterate the input array and keep track of three pointers.
The first pointer points to the candidate character.
The second pointer points to the index that can be overwritten.
The third pointer points to the last character which is same to the candidate.
Therefore, we can use these three pointers to do in-place exchange.
The time complexity is O(n) and the space complexity is O(1).
Code:
class Solution { public int compress(char[] chars) { int candidate_idx = 0; int i = 0; for (int j = 0; j < chars.length; j++) { if (j == chars.length - 1 || chars[j] != chars[j + 1]) { chars[i++] = chars[candidate_idx]; if (j > candidate_idx) { for (char c : ("" + (j - candidate_idx + 1)).toCharArray()) { chars[i++] = c; } } candidate_idx = j + 1; } } return i; } }
