Leetcode 443. String Compression

Problem

Given an array of characters, compress it in-place using the following algorithm: replace each sequence of consecutive identical characters with the character followed by the number of times it appears. If a character appears only once, do not include the count. The function should modify the input array in-place and return the new length of the compressed array.

After compression, the first elements of the array (up to the returned length) should contain the compressed version. You do not need to worry about the contents of the array beyond the returned length.

Important: When a count has multiple digits (e.g., 12), each digit should be stored as a separate character in the array.

Requirements

1. Modify the input array in-place
2. Return the new length after compression
3. Use only O(1) extra space (excluding the input array)
4. Handle counts with multiple digits by storing each digit separately
5. Omit the count when a character appears exactly once

Constraints

• 1 ≤ chars.length ≤ 2000
• chars[i] is a lowercase English letter, uppercase English letter, digit, or symbol
• The input array must be modified in-place with O(1) extra memory

Examples

Example 1:

Input: chars = ['a','a','b','b','c','c','c'] Output: 6 Explanation: The first 6 characters of the array become ['a','2','b','2','c','3'] The groups are "aa", "bb", and "ccc", which compress to "a2", "b2", and "c3"

Example 2:

Input: chars = ['a'] Output: 1 Explanation: The array remains ['a'] since there's only one character

Example 3:

Input: chars = ['a','b','b','b','b','b','b','b','b','b','b','b','b'] Output: 4 Explanation: The first 4 characters become ['a','b','1','2'] The single 'a' stays as 'a', and the 12 'b's become 'b12' (stored as 'b', '1', '2')

Hint 1: Two-Pointer Approach Use one pointer to read through the array and another pointer to write the compressed result back to the same array. The write pointer will always be at or behind the read pointer, ensuring you don't overwrite data you haven't processed yet.

Hint 2: Counting Consecutive Characters For each group of consecutive identical characters, count how many times it appears. If the count is 1, just write the character. If the count is greater than 1, write the character followed by each digit of the count as separate characters.

Hint 3: Converting Numbers to Digits When you have a count like 12, you need to store '1' and '2' as separate characters. Convert the number to a string and iterate through each digit character, or use mathematical operations to extract each digit.

Full Solution ` def compress(chars): # Write pointer tracks where to write compressed data write = 0 # Read pointer tracks current position in original array read = 0

while read < len(chars):
    # Store the current character
    current_char = chars[read]
    # Count consecutive occurrences
    count = 0
    
    # Count all consecutive occurrences of current character
    while read < len(chars) and chars[read] == current_char:
        read += 1
        count += 1
    
    # Write the character
    chars[write] = current_char
    write += 1
    
    # If count > 1, write the count digits
    if count > 1:
        # Convert count to string to access each digit
        count_str = str(count)
        for digit_char in count_str:
            chars[write] = digit_char
            write += 1

# Return the length of compressed array
return write

`

Explanation:

The solution uses a two-pointer technique:

1. Read Pointer: Traverses the entire array to identify groups of consecutive identical characters
2. Write Pointer: Tracks where to write the compressed output in the same array

Algorithm Steps:

1. Initialize both pointers at the start of the array

2. For each group of consecutive characters:

   • Count how many times the character appears consecutively
   • Write the character at the write pointer position
   • If the count is greater than 1, convert the count to a string and write each digit character separately

3. Move the read pointer past all counted characters

4. Return the final write pointer position, which is the compressed length

Why This Works In-Place:

The write pointer is always at or behind the read pointer because compression never increases the array size. For example, "aaa" (3 characters) compresses to "a3" (2 characters), and "ab" (2 characters) stays as "ab" (2 characters, no count for single occurrences).

Time Complexity: O(n) where n is the length of the input array. We traverse the array once.

Space Complexity: O(1) as we only use a constant amount of extra space (two pointers and a few variables). The modification is done in-place on the input array.