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

Design Compressed String Iterator

Number: 604

Difficulty: Easy

Paid? Yes

Companies: Google

Problem Description

We are tasked with designing a compressed string iterator. The input is a compressed string where each character is immediately followed by a positive integer indicating how many times that character appears in the uncompressed string. The iterator should implement two methods: next(), which returns the next uncompressed character (or a white space if no characters remain), and hasNext(), which returns true if there are more characters to be iterated.

Key Insights

  • Parse the compressed string into segments of (character, count) pairs without decompressing the entire string.
  • Use two parallel arrays (or similar data structures) to store characters and their corresponding counts.
  • Maintain an index pointer to track the current segment and decrement the count as characters are emitted.
  • Handle numbers consisting of multiple digits carefully.

Space and Time Complexity

Time Complexity: O(1) per next() and hasNext() call on average. Space Complexity: O(n), where n is the number of unique character segments in the compressed string.

Solution

The solution first pre-parses the compressed string into a list of character and count pairs. This ensures we do not decompress the entire string, which could be enormous due to high repetition counts. The iterator uses an index pointer to track the current segment and decrements the count each time next() is called. Once a segment’s count is exhausted, the pointer moves to the next segment. Both next() and hasNext() operations run in constant time on average, making the solution efficient.

Code Solutions

All implementations follow a similar approach: parsing the input string to store character segments and counts, then using an index pointer to manage iteration.

class StringIterator:
    # Constructor to parse compressed string into list of characters and counts.
    def __init__(self, compressedString: str):
        self.chars = []  # List of characters.
        self.counts = [] # Corresponding counts for each character.
        self.index = 0   # Pointer to current segment.
        i = 0
        n = len(compressedString)
        # Parse the compressed string.
        while i < n:
            # The next character.
            char = compressedString[i]
            i += 1
            count = 0
            # Build the full number (could span multiple digits).
            while i < n and compressedString[i].isdigit():
                count = count * 10 + int(compressedString[i])
                i += 1
            self.chars.append(char)
            self.counts.append(count)
    
    # Return the next character, or a white space if none remain.
    def next(self) -> str:
        if not self.hasNext():
            return " "
        # Decrement count and return the appropriate character.
        self.counts[self.index] -= 1
        return self.chars[self.index]
    
    # Check if there is any remaining character.
    def hasNext(self) -> bool:
        # Skip any segments that are fully consumed.
        while self.index < len(self.counts) and self.counts[self.index] == 0:
            self.index += 1
        return self.index < len(self.counts)
← Back to All Questions