Problem Description

The "Compressed String Iterator" problem asks you to design an iterator to efficiently read characters from a compressed string. The compressed string consists of alternating characters and positive integer counts, such as "a2b3", which represents the uncompressed string "aabbb".

You must implement a class with two main methods:

• next(): Returns the next character in the uncompressed string, or a single space character ' ' if there are no more characters.
• hasNext(): Returns True if there are more characters to return, or False otherwise.

Thought Process

At first glance, you might consider decompressing the entire string and then simply iterating over it. However, this approach is inefficient if the counts are large, as it wastes memory and time. Instead, the goal is to process the compressed string "on the fly," expanding only as much as needed for each next() call.

The key realization is that we can keep track of the current character and how many times it should still be returned. When that count reaches zero, we move to the next character-number pair in the compressed string. This way, we avoid building the whole uncompressed string and only maintain a small amount of state.

Solution Approach

To solve this problem efficiently, we process the compressed string incrementally, keeping track of our position and the remaining count for the current character. Here’s how:

1. Initialization: Store the compressed string and set a pointer (index) at the start.
2. Parsing: Whenever we need a new character, parse the next character and its associated count from the current position. The count may have multiple digits (for example, "a12").
3. State Tracking: Keep two variables: one for the current character, and one for how many times it should still be returned (num_remaining).
4. next():
   • If num_remaining > 0, return the current character and decrement num_remaining.
   • If num_remaining == 0, parse the next character-number pair and repeat.
   • If there are no more pairs, return a space character ' '.
5. hasNext():
   • Return True if num_remaining > 0 or if there are more pairs to parse; otherwise, False.
6. Efficiency:
   • We only parse as much of the compressed string as needed, and never build the full uncompressed string.
   • Parsing counts with multiple digits requires looping over consecutive digit characters.

Example Walkthrough

Let's walk through the process using the compressed string "a2b3":

• Start: index = 0, current_char = '', num_remaining = 0
• First next() call:
  • num_remaining == 0, so parse: current_char = 'a', num_remaining = 2
  • Return 'a', now num_remaining = 1
• Second next() call:
  • num_remaining = 1, return 'a', now num_remaining = 0
• Third next() call:
  • num_remaining == 0, parse: current_char = 'b', num_remaining = 3
  • Return 'b', now num_remaining = 2
• Next two next() calls:
  • Return 'b' twice, num_remaining decrements to 0
• Final next() call:
  • No more pairs to parse, return ' '
• hasNext() returns False at this point.

Time and Space Complexity

• Brute-force Approach: Decompressing the entire string takes O(N) time and space, where N is the total length of the uncompressed string.
• Optimized Approach:
  • Each next() and hasNext() call is O(1) amortized, since parsing a character-number pair is proportional to the number of digits (which is at most log10 of the count).
  • Space complexity is O(1), since we only store the compressed string and a few counters, not the decompressed string.

Summary

The compressed string iterator problem encourages an efficient, on-the-fly approach to decompressing and iterating over a string. By parsing the compressed string as needed and keeping only minimal state, we avoid unnecessary memory usage and ensure fast iteration. The key insight is to process the string incrementally, only expanding each character the moment it is needed.

Code Implementation

class StringIterator:
    def __init__(self, compressedString: str):
        self.compressed = compressedString
        self.ptr = 0  # Pointer in compressed string
        self.char = ' '
        self.num_remaining = 0

    def _parse_next(self):
        if self.ptr >= len(self.compressed):
            return
        self.char = self.compressed[self.ptr]
        self.ptr += 1
        num = 0
        while self.ptr < len(self.compressed) and self.compressed[self.ptr].isdigit():
            num = num * 10 + int(self.compressed[self.ptr])
            self.ptr += 1
        self.num_remaining = num

    def next(self) -> str:
        if self.num_remaining == 0:
            self._parse_next()
        if self.num_remaining == 0:
            return ' '
        self.num_remaining -= 1
        return self.char

    def hasNext(self) -> bool:
        return self.num_remaining > 0 or self.ptr < len(self.compressed)
      

class StringIterator {
    string compressed;
    int ptr;
    char ch;
    int num_remaining;

    void parseNext() {
        if (ptr >= compressed.size()) return;
        ch = compressed[ptr++];
        int num = 0;
        while (ptr < compressed.size() && isdigit(compressed[ptr])) {
            num = num * 10 + (compressed[ptr++] - '0');
        }
        num_remaining = num;
    }
public:
    StringIterator(string compressedString) {
        compressed = compressedString;
        ptr = 0;
        ch = ' ';
        num_remaining = 0;
    }

    char next() {
        if (num_remaining == 0) {
            parseNext();
        }
        if (num_remaining == 0) return ' ';
        num_remaining--;
        return ch;
    }

    bool hasNext() {
        return num_remaining > 0 || ptr < compressed.size();
    }
};
      

class StringIterator {
    private String compressed;
    private int ptr;
    private char ch;
    private int numRemaining;

    public StringIterator(String compressedString) {
        compressed = compressedString;
        ptr = 0;
        ch = ' ';
        numRemaining = 0;
    }

    private void parseNext() {
        if (ptr >= compressed.length()) return;
        ch = compressed.charAt(ptr++);
        int num = 0;
        while (ptr < compressed.length() && Character.isDigit(compressed.charAt(ptr))) {
            num = num * 10 + (compressed.charAt(ptr++) - '0');
        }
        numRemaining = num;
    }

    public char next() {
        if (numRemaining == 0) {
            parseNext();
        }
        if (numRemaining == 0) return ' ';
        numRemaining--;
        return ch;
    }

    public boolean hasNext() {
        return numRemaining > 0 || ptr < compressed.length();
    }
}
      

var StringIterator = function(compressedString) {
    this.compressed = compressedString;
    this.ptr = 0;
    this.char = ' ';
    this.numRemaining = 0;
};

StringIterator.prototype._parseNext = function() {
    if (this.ptr >= this.compressed.length) return;
    this.char = this.compressed[this.ptr++];
    let num = 0;
    while (this.ptr < this.compressed.length && /\d/.test(this.compressed[this.ptr])) {
        num = num * 10 + parseInt(this.compressed[this.ptr]);
        this.ptr++;
    }
    this.numRemaining = num;
};

StringIterator.prototype.next = function() {
    if (this.numRemaining === 0) {
        this._parseNext();
    }
    if (this.numRemaining === 0) return ' ';
    this.numRemaining--;
    return this.char;
};

StringIterator.prototype.hasNext = function() {
    return this.numRemaining > 0 || this.ptr < this.compressed.length;
};