Design Compressed String Iterator

How it works

The most space-efficient approach avoids any preprocessing. We store the original compressed string and parse it lazily as we iterate. We keep track of the current character and how many times it should still be returned. When that count reaches zero, we parse the next character-count pair from the string on demand.

Steps

1. Store the compressed string. Initialize ptr = 0, num = 0, and ch = ' '.
2. For next(): If hasNext() is false, return a space. If num is 0, parse the next character (store in ch) and its following digits (store in num). Decrement num and return ch.
3. For hasNext(): Return true if ptr is less than the string length OR num is greater than 0.

Complexity

• Since no precomputation is done, constant space is required in this case.

• The time required to perform next() operation is O(1).

• The time required for hasNext() operation is O(1).

• Since no precomputations are done, and hasNext() requires only O(1) time, this solution is advantageous if hasNext() operation is performed most of the times.

• This approach can be extended to include previous() and hasPrevious() operations, but this will require the use of some additional variables.

Things to watch for

Not Handling Multi-Digit Counts

Counts can be more than one digit (e.g., "a12" means 12 a's). A common mistake is reading only a single digit.

Incorrect hasNext() Logic with Demand Computation

When using lazy parsing, hasNext() must check both whether unparsed string remains AND whether current character still has remaining count.

class StringIterator:
    
    def __init__(self, compressedString: str):
        self.res = compressedString
        self.ptr = 0
        self.num = 0
        self.ch = ' '
    
    def next(self) -> str:
        if not self.hasNext():
            return ' '
        
        if self.num == 0:
            self.ch = self.res[self.ptr]
            self.ptr += 1
            while self.ptr < len(self.res) and self.res[self.ptr].isdigit():
                self.num = self.num * 10 + int(self.res[self.ptr])
                self.ptr += 1

        self.num -= 1
        return self.ch
    
    def hasNext(self) -> bool:
        return self.ptr != len(self.res) or self.num != 0

class StringIterator {
public:
    string res;
    int ptr = 0, num = 0;
    char ch = ' ';
    
    StringIterator(string compressedString) {
        res = compressedString;
    }
    
    char next() {
        if (!hasNext())
            return ' ';

        if (num == 0) {
            ch = res[ptr++];
            while (ptr < res.length() && isdigit(res[ptr])) {
                num = num * 10 + (res[ptr++] - '0');
            }
        }
        
        num--;
        return ch;
    }
    
    bool hasNext() {
        return ptr != res.length() || num != 0;
    }
};