💬 Discord
Sign In
NeetCode #18LC-604EasyArrays & HashingNC Algo100
← Back to All Problems

#18 · #604 · Design Compressed String Iterator(迭代压缩字符串)

📌 Problem Statement & Constraints

Design and implement an iterator over a run-length encoded string, supporting next() (return the next character, or a single space " " if exhausted) and hasNext(). Constraints: the compressed string contains only letters and digits, with no leading zeros in the counts.

💡 Core Algorithmic Approaches

  1. Parse lazily: keep the current character, its remaining count, and the read position in the compressed string.
  2. A helper _parse() reads the next <letter><count> group and advances the position past the digits.
  3. next() returns the current character, decrements the count, and calls _parse() when the count hits zero.
  4. hasNext() is simply count > 0. Lazy parsing means the constructor is O(1) rather than O(|s|).

💻 Benchmark Python3 Implementation

class StringIterator:
    def __init__(self, compressedString: str):
        self.s = compressedString
        self.i = 0                         # read position in the compressed string
        self.ch = " "
        self.count = 0
        self._parse()

    def _parse(self) -> None:
        if self.i >= len(self.s):
            self.ch, self.count = " ", 0   # exhausted sentinel
            return
        self.ch = self.s[self.i]
        self.i += 1
        j = self.i
        while j < len(self.s) and self.s[j].isdigit():
            j += 1
        self.count = int(self.s[self.i:j])  # multi-digit counts are allowed
        self.i = j

    def next(self) -> str:
        if not self.hasNext():
            return " "
        self.count -= 1
        res = self.ch
        if self.count == 0:
            self._parse()                  # advance to the next group
        return res

    def hasNext(self) -> bool:
        return self.count > 0

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(1) amortised per next() call, plus O(number of digits) per group for parsing. The constructor is O(1) because parsing is lazy.
💾 Space Complexity
O(1): only the current group's state is retained, regardless of the compressed string's length.

⚠️ Interview Pitfalls & Follow-ups

  • Assuming the count is a single digit: run lengths can be multi-digit (e.g. a12), so the digit scan is required.
  • Returning " " from next() when exhausted but throwing elsewhere: the contract says return a single space, not raise.
  • Eagerly expanding the string in the constructor: O(expanded length) space and time, which defeats the purpose of the compressed representation.
  • Calling _parse() before decrementing the count: the current group's last character would be skipped.