LeetCode 604: Design Compressed String Iterator

Problem Restatement

We need to design a class called StringIterator.

The input is a compressed string. The compressed string has repeated groups of:

letter + positive integer

The integer tells us how many times that letter appears in the original uncompressed string.

For example:

"L1e2t1C1o1d1e1"

represents:

"LeetCode"

because:

The class must support two operations:

The official problem defines the compressed string as each letter followed by a positive integer, and asks us to implement next() and hasNext().

Input and Output

Constructor input:

StringIterator(compressedString)

Method outputs:

Example object usage:

iterator = StringIterator("L1e2t1C1o1d1e1")

Example

Calls:

StringIterator("L1e2t1C1o1d1e1")
next()
next()
next()
next()
next()
next()
hasNext()
next()
hasNext()

Output:

null
"L"
"e"
"e"
"t"
"C"
"o"
true
"d"
true

The iterator expands characters only when needed.

It does not need to build the full string "LeetCode" in memory.

First Thought: Fully Decompress the String

A simple approach is to expand the compressed string during initialization.

For example:

"a3b2"

becomes:

"aaabb"

Then next() just returns the next character from this expanded string.

This is easy, but it can waste memory.

For example:

"a1000000"

represents one million characters. Building that full string is unnecessary because the iterator may only ask for a few characters.

Key Insight

We should keep the compressed form and consume it lazily.

At any time, the iterator only needs to know:

When remaining becomes 0, we parse the next letter and its count.

This gives us an iterator that avoids full decompression.

Algorithm

Store the compressed string.

Initialize:

self.s = compressedString
self.index = 0
self.current_char = " "
self.remaining = 0

For next():

1. If hasNext() is false, return " ".
2. If remaining == 0, parse the next letter and its count from self.s.
3. Decrease remaining by 1.
4. Return current_char.

For hasNext():

Return true if either:

1. The current parsed character still has remaining copies.
2. There is still unparsed compressed input.

That condition is:

self.remaining > 0 or self.index < len(self.s)

Implementation

class StringIterator:

    def __init__(self, compressedString: str):
        self.s = compressedString
        self.index = 0
        self.current_char = " "
        self.remaining = 0

    def next(self) -> str:
        if not self.hasNext():
            return " "

        if self.remaining == 0:
            self.current_char = self.s[self.index]
            self.index += 1

            count = 0
            while self.index < len(self.s) and self.s[self.index].isdigit():
                count = count * 10 + int(self.s[self.index])
                self.index += 1

            self.remaining = count

        self.remaining -= 1
        return self.current_char

    def hasNext(self) -> bool:
        return self.remaining > 0 or self.index < len(self.s)

Code Explanation

The constructor stores the compressed string and initializes the iterator state:

self.s = compressedString
self.index = 0
self.current_char = " "
self.remaining = 0

The variable index points to the next unread position in the compressed string.

The variable remaining stores how many copies of current_char are still available.

The first check in next() handles exhaustion:

if not self.hasNext():
    return " "

If there are no more characters, the problem asks us to return a single white space.

When remaining == 0, the iterator needs to load a new compressed group:

self.current_char = self.s[self.index]
self.index += 1

After reading the letter, we parse all following digits:

count = 0
while self.index < len(self.s) and self.s[self.index].isdigit():
    count = count * 10 + int(self.s[self.index])
    self.index += 1

This supports multi-digit counts such as:

"a12"

After parsing the count, next() consumes one copy:

self.remaining -= 1
return self.current_char

The hasNext() method checks both already-parsed and not-yet-parsed characters:

return self.remaining > 0 or self.index < len(self.s)

This matters because the iterator may still have characters left in either place.

Correctness

The iterator processes the compressed string from left to right.

Whenever remaining == 0, it reads exactly one compressed group: one letter followed by its positive integer count. It stores the letter in current_char and stores the count in remaining.

Each call to next() returns current_char once and decreases remaining by one. Therefore, a group like a5 returns exactly five copies of "a".

After all copies of one group are consumed, remaining becomes zero, so the next call to next() parses the next compressed group.

Because groups are parsed in their original order, characters are returned in the same order as the uncompressed string.

If no parsed characters remain and no compressed input remains, hasNext() returns false, and next() returns " ". Therefore, the implementation matches the required iterator behavior.

Complexity

Let n be the length of compressedString.

Across all calls, every character in the compressed string is scanned at most once.

Alternative: Parse All Groups First

We can also parse the compressed string during initialization into pairs:

[("L", 1), ("e", 2), ("t", 1)]

Then next() walks through this list.

class StringIterator:

    def __init__(self, compressedString: str):
        self.groups = []
        self.pos = 0

        i = 0
        while i < len(compressedString):
            ch = compressedString[i]
            i += 1

            count = 0
            while i < len(compressedString) and compressedString[i].isdigit():
                count = count * 10 + int(compressedString[i])
                i += 1

            self.groups.append([ch, count])

    def next(self) -> str:
        if not self.hasNext():
            return " "

        ch, count = self.groups[self.pos]
        self.groups[self.pos][1] -= 1

        if self.groups[self.pos][1] == 0:
            self.pos += 1

        return ch

    def hasNext(self) -> bool:
        return self.pos < len(self.groups)

This version is simple, but it uses O(n) space for the parsed groups.

The lazy version above uses less extra space.

Testing

def run_tests():
    iterator = StringIterator("L1e2t1C1o1d1e1")

    assert iterator.next() == "L"
    assert iterator.next() == "e"
    assert iterator.next() == "e"
    assert iterator.next() == "t"
    assert iterator.next() == "C"
    assert iterator.next() == "o"
    assert iterator.hasNext() is True
    assert iterator.next() == "d"
    assert iterator.hasNext() is True
    assert iterator.next() == "e"
    assert iterator.hasNext() is False
    assert iterator.next() == " "

    iterator = StringIterator("a12")
    for _ in range(12):
        assert iterator.next() == "a"
    assert iterator.hasNext() is False
    assert iterator.next() == " "

    iterator = StringIterator("x1y1")
    assert iterator.hasNext() is True
    assert iterator.next() == "x"
    assert iterator.hasNext() is True
    assert iterator.next() == "y"
    assert iterator.hasNext() is False

    print("all tests passed")

run_tests()

Test coverage: