Design Compressed String Iterator - Solution & Explanation

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.