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 III

Difficulty: Medium

Problem Description

Given a string word, compress it using the following algorithm: Begin with an empty string comp. While word is not empty, remove a maximum length prefix of word made of a single character c repeating at most 9 times, and append the length of the prefix followed by c to comp. Return the string comp.

Key Insights

  • The problem requires compressing a string by counting consecutive characters and ensuring that the count does not exceed 9.
  • The compression algorithm processes the string in a single pass, focusing on contiguous segments of the same character.
  • Keeping track of the character and its count is essential to form the compressed string correctly.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the input string, as we traverse the string once. Space Complexity: O(1) for the variables used, and O(m) for the output string, where m is the length of the compressed string.

Solution

To solve this problem, we will use a simple iterative approach. We will traverse the input string while keeping track of the current character and its count. For each character, we will count how many times it appears consecutively (up to a maximum of 9). When a different character is encountered or the end of the string is reached, we will append the count and the character to the result string. This ensures that we construct the compressed format as specified.

Code Solutions

def compress(word: str) -> str:
    comp = []
    n = len(word)
    i = 0
    
    while i < n:
        char = word[i]
        count = 0
        
        # Count the number of consecutive characters
        while i < n and word[i] == char and count < 9:
            count += 1
            i += 1
        
        # Append the count and the character to the compressed string
        comp.append(str(count))
        comp.append(char)
    
    return ''.join(comp)
← Back to All Questions