443. String Compression Medium

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: Characters beyond the returned length in the array don't matter, they 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 1 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".

Approach

Input: A character array chars

Output: Length of the compressed array (modifying chars internally in-place)

This problem belongs to String problems.

Core Idea

Use Two Pointers:

• read pointer scans the character array, counting the occurrences of identical consecutive characters segment by segment.
• write pointer is responsible for writing the compression result back to the front of the array.

Steps

1. Initialize read and write to 0.
2. While read < n:
   • Define a temporary pointer i = read, moving right until encountering a different character, yielding the segment length cnt = i - read.
   • Write chars[read] to chars[write], and increment write.
   • If cnt > 1, convert cnt into a string and write digit by digit (ensuring each digit is a single character), while incrementing write.
   • Update read = i, continuing to process the next segment.
3. After traversal completes, return write as the compressed array limit's length.

Note Points

• Only when cnt > 1 is the count appended.
• Multi-digit numbers must be written character by character, e.g., 12 → '1', '2'.
• The function returns the new length limit, not the array object itself.

Implementation

python

from typing import List

class Solution:
    def compress(self, chars: List[str]) -> int:
        i = 0  # Pointer handling where to write compressed characters
        j = 0  # Pointer traversing the original array

        while j < len(chars):  # Traverse throughout the character array completely
            count = 0  # Counter keeping consecutive appearances
            curr = chars[j]  # Current processing element component character
            
            # Inner iterations loop counting identical adjacent continuous characters efficiently 
            while j < len(chars) and chars[j] == curr:
                j += 1  # Step iterator accurately
                count += 1  # Increment combinations appropriately count
            
            chars[i] = curr  # Store current characters safely
            i += 1  # Offset writing location smoothly
            
            # If appearances recorded properly greater than one
            if count > 1:
                for digit in str(count):  # Digest number digit explicitly converting iteratively string 
                    chars[i] = digit
                    i += 1  # Track location bounds actively advancing
        
        return i  # Return final written effective arrays length limit configurations

javascript

/**
 * @param {character[]} chars
 * @return {number}
 */
var compress = function(chars) {
    // If only one character, no compression needed, directly return 1
    if (chars.length === 1) return 1;
    const n = chars.length;

    let write = 0; // Write pointer: responsible for placing results back into the front of chars array
    let read = 0;  // Read pointer: starting point of the current character segment being processed

    // Traverse the entire character array
    while (read < n) {
        let i = read;

        // Find the right boundary of the same character segment starting from `read` (exclusive)
        // Namely, chars[read...i-1] are identical characters
        while (i < n && chars[read] === chars[i]) i++;
        const cnt = i - read; // Length of this identical character segment

        // 1. Write the character itself
        chars[write] = chars[read];
        write++;

        // 2. If the count is > 1, write its digits out
        if (cnt > 1) {
            for (let ch of String(cnt)) {
                chars[write] = ch; // Note: appending character by character ('1', '2'...)
                write++;
            }
        }

        // 3. Jump the read pointer to the next segment
        read = i;
    }

    // Return the effective length of the compressed array configuration limits
    return write;
};

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(1)

Links

443. String Compression (English)

443. 压缩字符串 (Chinese)