604. Design Compressed String Iterator

Problem¶

Implement StringIterator for a string encoded as letter/count pairs with positive, possibly multi-digit counts.

• next() returns the next decoded character, or " " when exhausted.
• hasNext() reports whether any decoded characters remain without consuming one.

Encoded:    "a2B1"
Calls:      hasNext  next  next  hasNext  next  hasNext  next
Returns:    True     "a"   "a"   True     "B"   False    " "

class StringIterator:
    def __init__(self, compressedString: str):
        pass

    def hasNext(self) -> bool:
        pass

    def next(self) -> str:
        pass

Key trick¶

Decode lazily: store the current character, its remaining count, and the position of the next encoded pair.

Trap¶

Counts can contain multiple digits; expanding the entire string wastes memory, and hasNext() must account for both remaining repetitions and unread pairs.

Why is it interesting?¶

It tests state management and lazy evaluation: a tiny encoding can represent billions of characters.

Python solution¶

class StringIterator:
    def __init__(self, compressedString: str):
        self.s = compressedString
        self.i = 0
        self.ch = ""
        self.cnt = 0

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

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

        if self.cnt == 0:
            # Load the next run only after the current run is exhausted.
            self.ch = self.s[self.i]
            self.i += 1

            # Read every digit of the repetition count.
            while self.i < len(self.s) and self.s[self.i].isdigit():
                self.cnt = self.cnt * 10 + int(self.s[self.i])
                self.i += 1

        self.cnt -= 1
        return self.ch

Time: Initialization and hasNext() take \(O(1)\). A next() call takes \(O(d)\) when reading a count with \(d\) digits, otherwise \(O(1)\). Under the given count bound, \(d \leq 10\), so each call is \(O(1)\).

Space: \(O(1)\) auxiliary space, excluding the stored input string.

Comment on my solution¶

Your lazy-state design and hasNext() condition are correct. The new-run branch needs these fixes:

• Use self.s and self.i; bare s and i are undefined there.
• Convert count digits to an integer before subtracting.
• Parse the full count rather than one digit, advancing self.i past all digits instead of always by two.

# WRONG
class StringIterator:
    def __init__(self, s):
        self.s = s
        self.i = 0
        self.cnt = 0
        self.ch = None

    def hasNext(self):
        return self.cnt > 0 or self.i < len(self.s)

    def next(self):
        if not self.hasNext():
            return " "
        if self.cnt:
            self.cnt -= 1
            return self.ch
        self.ch = s[i]
        self.cnt = s[i + 1] - 1 # because we consume one char immediately
        self.i += 2
        return self.ch

Extra¶

Problem description¶

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.