String Compression

Problem Statement

Given an array of characters chars, compress it using the following algorithms:

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 sshould not be returned separately, but instead, be stored in the input character arraychars.

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 algorithm that uses only constant extra space.

Note: The characters in the array beyond the returned length do not matter and should be ignored.

Examples

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 compress 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 compress to "ab12".

Constraints:

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

Different Approaches

1️⃣ Two Pointers (In-Place)

Intuition:

We need to:

1. Traverse the array.
2. For each group of repeated characters, write:
   1. The character.
   2. Its count (if >1), digit by digit.
3. Do everything in-place using two pointers:
   1. One pointer read scan the array.
   2. Another pointer write writes back compressed result.

Code:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int compress(vector<char>& chars) {
        int n = chars.size();
        int write = 0;  // position to write compressed result
        int read = 0;   // position to read characters
        
        while (read < n) {
            char currentChar = chars[read];
            int count = 0;
            
            // Count consecutive characters
            while (read < n && chars[read] == currentChar) {
                read++;
                count++;
            }
            
            // Write the character
            chars[write++] = currentChar;
            
            // Write the count if > 1
            if (count > 1) {
                string cnt = to_string(count);
                for (char c : cnt) {
                    chars[write++] = c;
                }
            }
        }
        
        return write;  // new length
    }
};

Complexity Analysis:

• Time Complexity:O(n)
  • We traverse the array once (O(n)), and writing counts takes at most O(log k) digits (where k is the count of a group).
  • Overall: O(n)
• Space Complexity:
  • We only use few variables, and write in-place.
  • O(1) extra space.