443. String Compression

Question

Given an array of characters chars , compress it using the following algorithm:
Begin with an empty string s . For each group of consecutive repeating characters in chars :

If the group's length is 1 , append the character to s .
Otherwise, append the character followed by the group's length.
The compressed string s should not be returned separately , but instead, be stored in the input character array chars . Note that group lengths that are 10 or longer will be split into multiple characters in chars .
After you are done modifying the input array, return the new length of the array .
You must write an algorithm that uses only constant extra space.
Note: The characters in the array beyond the returned length do not matter and should be ignored.
Example 1:

Input: chars = ["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: The groups are "aa", "bb", and "ccc". This compresses to "a2b2c3".

Example 2:

Input: chars = ["a"] Output: Return 1, and the first character of the input array should be: ["a"] Explanation: The only group is "a", which remains uncompressed since it's a single character.

Example 3:

Input: chars = ["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: The groups are "a" and "bbbbbbbbbbbb". This compresses to "ab12".

Constraints:

1 <= chars.length <= 2000
chars[i] is a lowercase English letter, uppercase English letter, digit, or symbol.

Solutions

int compress(vector<char>& chars) {
	// three pointer approach:
    // slow pointer points to the first element of the group.
    // fast pointer iterates through the whole array.
    // anchor points to the position need to encoding.
    // [0, slow) ensures the "chars" vector follow the encoding rule.
    // examples: ['a', 'b', 'b'] -> "ab2" -> return 3
    // examples: ['a', 'a', 'a', 'b', 'b'] -> "a3b2" -> return 4
    // Edge cases:
    // 1. when chars.size == 0, directly return 0;
    // 2. when all chars are distinct -> will return the chars.size and no
    // 3. long run, e.g. group size string is larger than 2, e.g. "b1c100"
    // encoding. 
    // Time Complexity: O(N) 
    // Space Complexity: O(1)
    int n = static_cast<int>(chars.size());
    if (n == 0)
      return 0;
    int slow = 0;
    int anchor = 0;
    for (int fast = 0; fast < n; ++fast) {
      // case: fast == n is to nofity fast has reach the last chars, need to force process the encoding.
      if (chars[fast] != chars[slow]) {
        int distance = fast - slow;
        chars[anchor++] = chars[slow];
        if (distance > 1) {
          // in case when distance > 1
          string distanceStr = to_string(distance);
          for (const auto &c : distanceStr) {
            chars[anchor++] = c;
          }
        }
        // make slow point catch up fast's group first element.
        slow = fast;
      }
    }

    // dont forget there's the last round.
    int distance = n - slow;
    chars[anchor++] = chars[slow];
    if (distance > 1) {
      string distanceStr = to_string(distance);
      for (const auto& c: distanceStr) {
        chars[anchor++] = c;
      }
    }

    // anchor will points to the next position of the last encoding chars. which
    // can be the length.
    return anchor;
}