Day 6: String Compression (LeetCode 443)

Problem Overview

The task is to compress a given array of characters in-place. For each group of consecutive repeating characters:

• If the character appears once, it remains unchanged.
• If it appears multiple times, append the character followed by its frequency.

The result must be stored in the same array, and the function should return the new length of the compressed array. The solution must use constant extra space.

---

Approach

To solve this problem efficiently, we use a two-pointer technique:

• A read pointer (i) to traverse the array.
• A write pointer (index) to overwrite the array with the compressed result.

Steps:

1. Initialize index = 0 to track the position for writing.
2. Traverse the array using pointer i.
3. For each character:

• Count how many times it appears consecutively.
• Write the character at index.

• If the count is greater than 1:

  • Convert the count to a string.
  • Write each digit of the count into the array.
    1. Continue until the entire array is processed.
    2. Return the final value of index.

---

Code Implementation (C++)

class Solution {
public:
    int compress(vector<char>& s) {
        int n = s.size();
        int index = 0;

        for(int i = 0; i < n; ) {
            char curr = s[i];
            int count = 0;

            while(i < n && s[i] == curr) {
                i++;
                count++;
            }

            s[index++] = curr;

            if(count > 1) {
                string cnt = to_string(count);
                for(char c : cnt) {
                    s[index++] = c;
                }
            }
        }

        return index;
    }
};

---

Example

Input:

["a","a","b","b","c","c","c"]

Output:

["a","2","b","2","c","3"]

Returned Length: 6

---

Complexity Analysis

• Time Complexity: O(n)
  Each element is processed once.

• Space Complexity: O(1)
  The compression is done in-place without extra memory.

---

Key Insights

• The two-pointer approach allows efficient in-place updates.
• Converting counts to strings ensures correct handling of multi-digit frequencies.
• Careful index management is crucial to avoid overwriting data incorrectly.

---