Domain 2MediumCORE

String Compression

We are given a mutable character array (chars) and need to compress consecutive repeating characters in-place. - Input: A list of single-character strings (e.g., ['a', 'b']). Constraints: length 1 to 2000, chars can be letters/digits/symbols. - Output: An integer representing the new compressed length. The input array must be modified such that its first N elements contain the compressed string. - Logic: Iterate through groups of identical consecutive characters. If a group has length k: - Append the character once. - If k > 1, append digits of k immediately after the character. - Edge Cases: Single characters (no count appended), counts >= 10 (digits split into multiple chars in array).

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#String

443. String Compression

Model: qwen3.5:9b
Topics: String
FAANG asked: 1
Acceptance rate: 44.1%


Problem Breakdown

We are given a mutable character array (chars) and need to compress consecutive repeating characters in-place.

  • Input: A list of single-character strings (e.g., ["a", "b"]). Constraints: length 1 to 2000, chars can be letters/digits/symbols.
  • Output: An integer representing the new compressed length. The input array must be modified such that its first N elements contain the compressed string.
  • Logic: Iterate through groups of identical consecutive characters. If a group has length k:
    • Append the character once.
    • If k > 1, append digits of k immediately after the character.
  • Edge Cases: Single characters (no count appended), counts >= 10 (digits split into multiple chars in array).

Intuition

A naive approach might be to build a new string or list, then copy it back over the input array. While this is O(N) time, allocating an auxiliary buffer of size N violates the follow-up constraint for O(1) extra space.

To achieve O(1) space (excluding output storage), we must modify the existing chars array directly without creating a new list of characters. The key insight here is using two pointers:

  1. A read pointer (i) to identify groups and count duplicates in the original data.
  2. A write pointer (j or idx) that tracks where we are placing the compressed result within the same array.

Since compression reduces (or keeps equal) the length of a group compared to its raw character representation, the write index will generally lag behind the read index. This allows us to overwrite characters safely as long as we process groups sequentially from left to right without skipping unread data that hasn’t been processed yet. We only need integer counters for lengths and indices.

Approach

  1. Initialize write_idx at 0 (the position where next character goes).
  2. Iterate through the array using a pointer i. For each group starting at i:
    • Count consecutive identical characters until a different one is found or end of list. Let this count be count.
  3. Update the array:
    • Always write the current character (chars[i]) to chars[write_idx] and increment write_idx.
    • If count > 1, convert count to a string (e.g., “2”, “10”). Iterate over each digit of that number, writing it to chars[write_idx] sequentially. Increment write_idx for every digit written.
  4. Move the read pointer (i) past this group so we don’t re-process these characters in subsequent iterations (since they are now consumed).
  5. Return write_idx.

Complexity Analysis

  • Time: O(N), where N is the length of chars. We traverse the array once to count groups and write digits. Converting a number to string takes logarithmic time relative to its value, but since max group size <= N (2000), this adds negligible overhead per group compared to linear traversal.
  • Space: O(1) extra space. We use only integer variables (i, j, count) and do not allocate a new array proportional to input size.

Solution

def compress(chars):
    write_idx = 0
    n = len(chars)
    
    i = 0
    while i < n:
        j = i + 1
        count = 1
        
        # Count consecutive duplicates starting at current group start 'i'
        while j < n and chars[j] == chars[i]:
            count += 1
            j += 1
            
        # Write the character itself first (always)
        if write_idx != i: 
             pass # Logic ensures we overwrite safely, but strictly speaking 
                   # we just place at current write position.
        
        chars[write_idx] = chars[i]
        write_idx += 1
        
        # If count > 1, append digits of the length
        if count > 1:
            for digit in str(count):
                chars[write_idx] = digit
                write_idx += 1
            
        # Move read pointer to end of current group (j)
        i = j
        
    return write_idx

# Example usage / verification logic would go here, but function is self-contained.

Edge Cases Handled

  • Single Character Groups: Logic checks count > 1 before appending digits; if count is 1, only the character itself is written to the array at that position.
  • Multi-Digit Counts (>= 10): Converting integer count to string handles this naturally (e.g., “a” + ‘1’ + ‘2’). The loop iterates over each digit in str(count) and writes them sequentially into chars.
  • Empty Input: Constraint guarantees length >= 1, but the logic holds for empty lists returning 0 implicitly if list is empty.
  • Mixed Duplicates (e.g., “aa…b”): The loop resets at every group boundary (i = j), ensuring independent groups of same characters are handled correctly without merging counts across different segments.