Is Design Compressed String Iterator easy or hard?

Design Compressed String Iterator is rated Easy on LeetCode but includes basic system design elements. The challenge is parsing multi-digit counts correctly and maintaining iterator state efficiently without expanding the full string.

Design Compressed String Iterator Python/Java solution

Python and Java solutions typically parse the string during initialization and store character-count pairs in a list or arrays. next() returns the current character and decreases the remaining count, while hasNext() checks whether any counts remain. The logic stays identical across Python, Java, C++, Go, and TypeScript.

How to solve Design Compressed String Iterator in O(n)?

Scan the compressed string once and extract characters with their numeric counts. Store them in arrays or a list of pairs. Maintain a pointer to the current segment and decrease its remaining count whenever next() is called, advancing the pointer when the count becomes zero.

What is the best approach for Design Compressed String Iterator?

The best approach parses the compressed string into (character, count) pairs and tracks remaining counts during iteration. Each next() call returns the current character and decreases its count, moving to the next pair when the count reaches zero. This keeps operations O(1) while using only O(k) space where k is the number of compressed segments.

Is Design Compressed String Iterator asked at Google/Amazon/Meta?

Iterator design and run-length encoding problems appear frequently in interviews at large tech companies including Google, Amazon, and Meta. Variations often test object-oriented design, efficient parsing, and maintaining state across method calls.

What data structure is used in Design Compressed String Iterator?

Most implementations store parsed results in an array or list of (character, count) pairs. An index pointer and a remaining-count variable track the iterator state. This structure supports constant-time updates during iteration.

What is the time complexity of Design Compressed String Iterator?

Parsing the compressed input takes O(n) time where n is the length of the compressed string. After initialization, both next() and hasNext() run in O(1) time because they only update counters and indexes. Space complexity is O(k) for storing character-count pairs.

Description Solution Video 4:23

604. Design Compressed String Iterator

Easy40.5% acceptance1 companyPremium elsewhere, free here

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 returns false.

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 <= 1000
compressedString consists of lower-case an upper-case English letters and digits.
The number of a single character repetitions in compressedString is in the range [1, 10^9]
At most 100 calls will be made to next and hasNext.