We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

String Compression

Difficulty: Medium

Problem Description

Given an array of characters chars, compress it using the following algorithm: For each group of consecutive repeating characters in chars, if the group’s length is 1, append the character to a new string. Otherwise, append the character followed by the group’s length. The compressed string should be stored in the input character array chars, and the function should return the new length of the array.

Key Insights

  • The problem requires modifying the original array in place, which entails careful management of indices.
  • We need to account for character groups of varying lengths and represent lengths greater than 1 with multiple characters.
  • The solution must achieve this with constant extra space.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the input array chars. Each character is processed at most twice. Space Complexity: O(1), as we are modifying the input array in place without using additional data structures.

Solution

The solution uses a two-pointer approach to iterate through the array while compressing it in place. The first pointer (read) traverses the input array, while the second pointer (write) keeps track of where to write the compressed characters. For each group of consecutive characters, we determine the count, write the character, and if the count is greater than 1, write the count as well. Finally, we return the length of the modified part of the array.

Code Solutions

def compress(chars):
    write = 0  # Pointer to write the compressed characters
    read = 0   # Pointer to read the original characters

    while read < len(chars):
        char = chars[read]
        count = 0
        
        # Count the number of occurrences of the current character
        while read < len(chars) and chars[read] == char:
            read += 1
            count += 1
        
        # Write the character to the write pointer
        chars[write] = char
        write += 1
        
        # Write the count if greater than 1
        if count > 1:
            for digit in str(count):
                chars[write] = digit
                write += 1
                
    return write
← Back to All Questions