604. Design Compressed String Iterator
Model: qwen2.5-coder:14b
Topics: Design
FAANG asked: 1
Acceptance rate: 38.3%
Problem Breakdown
The problem requires designing a data structure to iterate over an uncompressed version of a compressed string. The input is a string where each character is followed by a positive integer indicating how many times that character appears consecutively in the original string. The output should be able to provide the next character in the sequence and check if there are more characters left.
Inputs:
- A compressed string, e.g., “L1e2t1C1o1d1e1”.
Outputs:
next(): Returns the next character in the uncompressed string or a space character if no more characters are available.hasNext(): ReturnsTrueif there are more characters to be returned, otherwiseFalse.
Implicit Constraints/Edge Cases:
- The number of repetitions can be up to 10^9, which means we need an efficient way to handle large counts without storing all characters explicitly.
- The input string is non-empty and well-formed.
Intuition
A brute-force approach would involve expanding the entire compressed string into its uncompressed form and then iterating over it. However, this is inefficient in terms of both time and space complexity, especially given the potential size of the repetitions.
The key insight is to parse the compressed string once and store the characters along with their counts. We can then use a pointer to keep track of our current position in the sequence. This approach allows us to efficiently retrieve the next character without expanding the entire string.
Approach
-
Initialization:
- Parse the input compressed string to extract characters and their corresponding counts.
- Store these in two lists: one for characters and another for their respective counts.
- Initialize a pointer to keep track of the current position in these lists.
-
next() Method:
- If there are no more characters (i.e., the pointer has reached the end of the list), return a space character.
- Otherwise, decrement the count of the current character.
- If the count reaches zero, move the pointer to the next character and its count.
- Return the current character.
-
hasNext() Method:
- Check if the pointer is within bounds (i.e., there are still characters left to iterate over).
Complexity Analysis
-
Time Complexity:
- Initialization: O(n), where n is the length of the compressed string.
next()andhasNext(): O(1) for each call, as they involve simple list access and pointer manipulation.
-
Space Complexity:
- O(m), where m is the number of unique characters in the compressed string. This is because we store each character and its count separately.
Solution
class StringIterator:
def __init__(self, compressedString: str):
self.chars = []
self.counts = []
i = 0
while i < len(compressedString):
char = compressedString[i]
num_str = ""
i += 1
while i < len(compressedString) and compressedString[i].isdigit():
num_str += compressedString[i]
i += 1
self.chars.append(char)
self.counts.append(int(num_str))
self.index = 0
def next(self) -> str:
if not self.hasNext():
return ' '
char = self.chars[self.index]
self.counts[self.index] -= 1
if self.counts[self.index] == 0:
self.index += 1
return char
def hasNext(self) -> bool:
return self.index < len(self.chars)
Edge Cases Handled
- Empty Input: The constructor handles an empty string by initializing empty lists for characters and counts.
- Single Character with Large Count: The solution efficiently handles large counts without storing all characters, relying on the count to determine when to move to the next character.
- Sequential Calls to
next()andhasNext(): The methods are designed to work together correctly, ensuring thathasNext()accurately reflects whether there are more characters to return.