Design Compressed String Iterator - Video Solutions
LeetCode 604. Design Compressed String Iterator Explanation and Solution
Design Compressed String Iterator - Video Solution
Watch 4 video solutions for Design Compressed String Iterator, a easy level problem involving Array, String, Design. This walkthrough by happygirlzt has 914 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
Design and implement a data structure for a compressed string iterator. The given compressed string will be in the form of each letter followed by a positive integer representing the number of this letter existing in the original uncompressed string.
Implement the StringIterator class:
next()Returns the next character if the original string still has uncompressed characters, otherwise returns a white space.hasNext()Returns true if there is any letter needs to be uncompressed in the original string, otherwise returnsfalse.
Example 1:
Input
["StringIterator", "next", "next", "next", "next", "next", "next", "hasNext", "next", "hasNext"]
[["L1e2t1C1o1d1e1"], [], [], [], [], [], [], [], [], []]
Output
[null, "L", "e", "e", "t", "C", "o", true, "d", true]
Explanation
StringIterator stringIterator = new StringIterator("L1e2t1C1o1d1e1");
stringIterator.next(); // return "L"
stringIterator.next(); // return "e"
stringIterator.next(); // return "e"
stringIterator.next(); // return "t"
stringIterator.next(); // return "C"
stringIterator.next(); // return "o"
stringIterator.hasNext(); // return True
stringIterator.next(); // return "d"
stringIterator.hasNext(); // return True
Constraints:
1 <= compressedString.length <= 1000compressedStringconsists of lower-case an upper-case English letters and digits.- The number of a single character repetitions in
compressedStringis in the range[1, 10^9] - At most
100calls will be made tonextandhasNext.
Approach Overview
Problem Overview: You receive a run-length encoded string such as a2b3 where characters are followed by counts. Build an iterator that returns the next character in the decompressed sequence using next() and checks availability using hasNext() without explicitly storing the full expanded string.
Approach 1: Fully Decompress the String (O(n) time, O(n) space)
The most direct solution expands the compressed string into a normal string during initialization. Iterate through the input, parse each character and its numeric count, then append the character count times to a buffer. The iterator simply moves a pointer across this expanded string for next() while hasNext() checks if the pointer is within bounds. This works but wastes memory when counts are large since the decompressed string could be huge compared to the compressed input.
Approach 2: Parsing and Storing Character Counts (O(n) preprocessing, O(1) per operation, O(k) space)
Instead of expanding the string, parse the compressed input once and store pairs of (character, remainingCount). Maintain an index pointing to the current character block. When next() is called, return the current character and decrement its remaining count. If the count reaches zero, advance the index to the next pair. The hasNext() method checks whether the current index is still within the parsed array. This keeps memory proportional to the number of compressed segments rather than the full expanded length.
This approach is a classic design problem where the constructor performs parsing and the iterator methods maintain internal state. It also demonstrates efficient handling of run-length encoding using basic string parsing and sequential access patterns similar to an array iterator.
Recommended for interviews: The parsing-and-count-tracking approach is what interviewers expect. It avoids unnecessary memory allocation while keeping each iterator operation constant time. Mentioning the naive decompression method first shows you understand the problem baseline, but implementing the count-based iterator demonstrates stronger design and efficiency skills.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Fully Decompress String | O(n + totalExpanded) | O(totalExpanded) | Simple implementation when counts are small and memory is not a concern |
| Parse and Store Character Counts | O(n) preprocessing, O(1) per operation | O(k) | Preferred approach for large counts or memory-constrained scenarios |