Skip to main content
Talentd

Design Compressed String Iterator - Solution & Explanation

EasyPremiumFree on FleetCodeArrayStringDesignIterator6 min readAsked at: Google
Practice this problem

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

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.

Solution

Parse the compressedString into characters c and their corresponding repetition counts x, and store them in an array or list d. Use p to point to the current character.

Then perform operations in next and hasNext.

The initialization time complexity is O(n), and the time complexity of the other operations is O(1). Here, n is the length of compressedString.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Fully Decompress StringO(n + totalExpanded)O(totalExpanded)Simple implementation when counts are small and memory is not a concern
Parse and Store Character CountsO(n) preprocessing, O(1) per operationO(k)Preferred approach for large counts or memory-constrained scenarios

Video Solution

LeetCode 604. Design Compressed String Iterator Explanation and Solution • happygirlzt • 914 views views

Watch 3 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Design Compressed String Iterator with our built-in code editor and test cases.

Practice on FleetCode
Previous

LRU Cache

Next

String Compression