Design Compressed String Iterator

easy design string iterator

Problem

Implement next() and hasNext() on a compressed string like 'L1e2t1C1o1d1e1' → 'L','e','e','t','C','o','d','e'.

Inputinit('L1e2t1') next() next() next() hasNext()

Output'L' 'e' 'e' True

Decompress on the fly via (char, run_length).

input

class StringIterator:
    def __init__(self, s):
        import re
        self.toks = re.findall(r'([A-Za-z])(\d+)', s)
        self.i = 0; self.count = 0; self.ch = ' '
    def next(self):
        if not self.hasNext(): return ' '
        if self.count == 0:
            self.ch, c = self.toks[self.i]; self.count = int(c); self.i += 1
        self.count -= 1; return self.ch
    def hasNext(self):
        return self.count > 0 or self.i < len(self.toks)

class StringIterator {
  constructor(s) {
    this.toks = [...s.matchAll(/([A-Za-z])(\d+)/g)].map(m => [m[1], +m[2]]);
    this.i = 0; this.count = 0; this.ch = ' ';
  }
  next() {
    if (!this.hasNext()) return ' ';
    if (this.count === 0) { [this.ch, this.count] = this.toks[this.i++]; }
    this.count--; return this.ch;
  }
  hasNext() { return this.count > 0 || this.i < this.toks.length; }
}

class StringIterator {
    List toks = new ArrayList<>();
    int i = 0, count = 0; char ch = ' ';
    public StringIterator(String s) {
        int k = 0, n = s.length();
        while (k < n) {
            char c = s.charAt(k++); int v = 0;
            while (k < n && Character.isDigit(s.charAt(k))) v = v * 10 + s.charAt(k++) - '0';
            toks.add(new char[]{c, (char) v});
        }
    }
    public char next() {
        if (!hasNext()) return ' ';
        if (count == 0) { ch = toks.get(i)[0]; count = toks.get(i)[1]; i++; }
        count--; return ch;
    }
    public boolean hasNext() { return count > 0 || i < toks.size(); }
}

class StringIterator {
    vector> toks; int i = 0, count = 0; char ch = ' ';
public:
    StringIterator(string s) {
        int k = 0, n = s.size();
        while (k < n) {
            char c = s[k++]; int v = 0;
            while (k < n && isdigit(s[k])) v = v * 10 + s[k++] - '0';
            toks.push_back({c, v});
        }
    }
    char next() {
        if (!hasNext()) return ' ';
        if (count == 0) { ch = toks[i].first; count = toks[i].second; i++; }
        count--; return ch;
    }
    bool hasNext() { return count > 0 || i < (int)toks.size(); }
};

Explanation

The input is a compressed string like L1e2t1, where each letter is followed by a number telling how many times it repeats. Instead of expanding the whole thing into a long string up front, we decode it lazily as the caller asks for characters.

First we split the string into (char, count) tokens. In Python this is one regex: re.findall(r'([A-Za-z])(\d+)', s) gives a list like [('L','1'),('e','2'),('t','1')]. We keep a pointer i into that token list plus the current character ch and how many of it remain in count.

Every next() call works like a tiny vending machine. If count has dropped to 0, we pull the next token, set ch and count from it, and advance i. Then we hand back ch and decrement count by one.

hasNext() is true whenever the current run still has letters left (count > 0) or there are more tokens to read (i < len(toks)).

Example on L1e2t1: the first next() loads ('L',1) and returns L; the next loads ('e',2) and returns e; the next still has e pending so it returns e again. After that hasNext() is still true because the t token is waiting.

Time: O(1) amortized Space: O(k)