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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

String Compression III

Number: 3451

Difficulty: Medium

Paid? No

Companies: Google, Amazon, Microsoft, Apple, Affirm, Qualcomm

Problem Description

Given a string, compress it by repeatedly removing the longest possible prefix consisting of a single repeated character (up to 9 repetitions) and appending the count followed by the character to a result string. Continue this process until the original string is fully processed.

Key Insights

  • Iterate through the string while maintaining a pointer.
  • For each character encountered, count consecutive occurrences but cap the count at 9.
  • This ensures that even if a character repeats more than 9 times consecutively, it is split into multiple segments.
  • Append the count and the character to the result string in each iteration.
  • The approach requires a single pass through the string.

Space and Time Complexity

Time Complexity: O(n) where n is the length of the input string. Space Complexity: O(n) for the output string in the worst case when no compression occurs.

Solution

The solution uses a simple iterative approach with a pointer that traverses the string. For each character, it counts its consecutive appearances using a while loop, ensuring that at most 9 characters are counted in one iteration. After counting, it appends the count and the current character to the result. The process repeats until the entire string is processed. The primary data structures used are the string for output and simple integer counters for counting repetitions.

Code Solutions

# Function to compress the string following the described algorithm
def compress_string(word):
    # Initialize the result string and the index pointer
    compressed = ""
    i = 0
    n = len(word)
    
    # Process the input string until all characters are processed
    while i < n:
        # Set the current character and initialize count
        current_char = word[i]
        count = 0
        
        # Count consecutive occurrences up to 9
        while i < n and word[i] == current_char and count < 9:
            count += 1
            i += 1
        
        # Append the count and character to the compressed result
        compressed += str(count) + current_char
    
    return compressed

# Example usage:
word = "aaaaaaaaaaaaaabb"
print(compress_string(word))  # Output: "9a5a2b"
← Back to All Questions