Design Compressed String Iterator

LeetCode 604: Design Compressed String Iterator Solution & Explanation

Problem Overview

TL;DR: The optimal solution maintains a pointer to the current position in the compressed string and a counter for the current character's remaining occurrences, allowing strictly $O(1)$ memory usage.

The Design Compressed String Iterator problem asks us to create a class that iterates over an uncompressed version of a string provided in a compressed format. The format consists of a character followed by its frequency (e.g., "L1e2t1C1o1d1e1" represents "LeetCode"). We must implement next() to return the next character in the sequence and hasNext() to verify if characters remain, all without explicitly expanding the string into memory.

This is a popular interview question for companies like Google and Amazon because it tests object-oriented design skills and the ability to handle data streams efficiently under memory constraints.

Brute Force Approach for Design Compressed String Iterator

The naive approach is to fully decompress the string during initialization. We parse the input string, repeat each character the specified number of times, and store the result in a new string or character array. We then maintain a simple integer index to track our position in this decompressed string.

Pseudo-code:

Class StringIterator:
    string decompressed = ""
    int index = 0

    Constructor(compressedString):
        For each group (char c, int count) in compressedString:
            Append c to decompressed count times

    next():
        If index < decompressed.length:
            return decompressed[index++]
        Else:
            return ' '

    hasNext():
        return index < decompressed.length

Why this fails: While this logic is correct, it fails on Space Complexity. If the compressed string is "a1000000000", the brute force approach attempts to allocate memory for 1 billion characters, likely causing a Memory Limit Exceeded (MLE) error or crashing the application. The problem explicitly requires iterating without decompressing the entire string.

Algorithm Strategy: Design Patterns

To implement the Design Compressed String Iterator efficiently, we will maintain the following state variables:

1. res: A reference or copy of the original compressed string.
2. ptr: An integer index pointing to the current position in res that we are parsing.
3. current_char: The character currently being returned by the iterator.
4. current_count: The number of times current_char still needs to be returned.

Initialization:

• Store the compressed string.
• Set ptr to 0.
• Set current_count to 0.

Logic for next():

• Check if current_count is 0.
  • If yes, we need to fetch the next group. Check if ptr is at the end of the string.
    • If ptr is at the end, return a space ' '.
    • Otherwise, read the character at ptr into current_char and increment ptr.
    • Parse the number immediately following the character to update current_count.
• Decrement current_count.
• Return current_char.

Logic for hasNext():

• Return true if current_count > 0 OR if ptr is not at the end of the string.

Execution Flow

Let's trace the execution for input "L1e2":

1. Initialization: ptr = 0, current_count = 0, res = "L1e2".
2. Call next():
   • current_count is 0. We need to load data.
   • Read res[0] ('L'). Set current_char = 'L'. Increment ptr to 1.
   • Read number starting at res[1]. It's '1'. Set current_count = 1. Update ptr to 2.
   • Decrement current_count (now 0).
   • Return 'L'.
3. Call next():
   • current_count is 0. We need to load data.
   • Read res[2] ('e'). Set current_char = 'e'. Increment ptr to 3.
   • Read number starting at res[3]. It's '2'. Set current_count = 2. Update ptr to 4.
   • Decrement current_count (now 1).
   • Return 'e'.
4. Call next():
   • current_count is 1 (non-zero).
   • No parsing needed.
   • Decrement current_count (now 0).
   • Return 'e'.
5. Call hasNext():
   • current_count is 0.
   • ptr (4) is equal to string length (4).
   • Return false.

Proof of Correctness

The algorithm is correct because it sequentially processes the compressed format, respecting the order of groups (char + count). By strictly adhering to the count provided in the compressed string, it yields the exact number of characters specified. The state transition logic handles the boundary between groups (when count becomes 0) and the boundary of the entire string (when ptr reaches the end), ensuring no characters are skipped and no extra characters are generated.

Pattern Reuse Notes

The Design pattern, specifically involving state management for data structures, is applicable to several other famous LeetCode problems:

• LeetCode 146: LRU Cache - Requires maintaining state (access order) and value storage efficiently, similar to how we manage iterator state.
• LeetCode 155: Min Stack - Decorates a standard stack with additional state (minimum values) to support $O(1)$ retrieval.
• LeetCode 225: Implement Stack using Queues - Manipulates internal data structures to mimic the behavior of another, strictly following interface constraints.
• LeetCode 232: Implement Queue using Stacks - Similar to 225, this enforces specific behavioral patterns using restricted underlying storage.

In all these cases, the challenge is not just the algorithm, but the design of the class to meet specific time/space complexity requirements for its operations.

Reference Implementation

C++ Solution for LeetCode 604

1class StringIterator {
2private:
3    string res;
4    int ptr;
5    char current_char;
6    long long current_count;
7
8public:
9    StringIterator(string compressedString) {
10        res = compressedString;
11        ptr = 0;
12        current_char = ' ';
13        current_count = 0;
14    }
15    
16    char next() {
17        if (!hasNext()) return ' ';
18        
19        if (current_count == 0) {
20            current_char = res[ptr++];
21            long long num = 0;
22            while (ptr < res.length() && isdigit(res[ptr])) {
23                num = num * 10 + (res[ptr] - '0');
24                ptr++;
25            }
26            current_count = num;
27        }
28        
29        current_count--;
30        return current_char;
31    }
32    
33    bool hasNext() {
34        return current_count > 0 || ptr < res.length();
35    }
36};

Java Solution for LeetCode 604

1class StringIterator {
2    private String res;
3    private int ptr;
4    private char currentChar;
5    private long currentCount;
6
7    public StringIterator(String compressedString) {
8        this.res = compressedString;
9        this.ptr = 0;
10        this.currentChar = ' ';
11        this.currentCount = 0;
12    }
13    
14    public char next() {
15        if (!hasNext()) {
16            return ' ';
17        }
18        
19        if (currentCount == 0) {
20            currentChar = res.charAt(ptr++);
21            long num = 0;
22            while (ptr < res.length() && Character.isDigit(res.charAt(ptr))) {
23                num = num * 10 + (res.charAt(ptr) - '0');
24                ptr++;
25            }
26            currentCount = num;
27        }
28        
29        currentCount--;
30        return currentChar;
31    }
32    
33    public boolean hasNext() {
34        return currentCount > 0 || ptr < res.length();
35    }
36}

Python Solution for LeetCode 604

1class StringIterator:
2
3    def __init__(self, compressedString: str):
4        self.res = compressedString
5        self.ptr = 0
6        self.current_char = ' '
7        self.current_count = 0
8
9    def next(self) -> str:
10        if not self.hasNext():
11            return ' '
12        
13        if self.current_count == 0:
14            self.current_char = self.res[self.ptr]
15            self.ptr += 1
16            
17            # Parse the number
18            num_str = ""
19            while self.ptr < len(self.res) and self.res[self.ptr].isdigit():
20                num_str += self.res[self.ptr]
21                self.ptr += 1
22            self.current_count = int(num_str)
23            
24        self.current_count -= 1
25        return self.current_char
26
27    def hasNext(self) -> bool:
28        return self.current_count > 0 or self.ptr < len(self.res)