Problem

Design and implement a data structure for a compressed string iterator. The given compressed string will be in the form of each letter followed by a positive integer representing the number of this letter existing in the original uncompressed string.

Implement the StringIterator class:

  • next() Returns the next character if the original string still has uncompressed characters, otherwise returns a white space.
  • hasNext() Returns true if there is any letter needs to be uncompressed in the original string, otherwise returns false.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

**Input**
["StringIterator", "next", "next", "next", "next", "next", "next", "hasNext", "next", "hasNext"]
[["L1e2t1C1o1d1e1"], [], [], [], [], [], [], [], [], []]
**Output**
[null, "L", "e", "e", "t", "C", "o", true, "d", true]
**Explanation**
StringIterator stringIterator = new StringIterator("L1e2t1C1o1d1e1");
stringIterator.next(); // return "L"
stringIterator.next(); // return "e"
stringIterator.next(); // return "e"
stringIterator.next(); // return "t"
stringIterator.next(); // return "C"
stringIterator.next(); // return "o"
stringIterator.hasNext(); // return True
stringIterator.next(); // return "d"
stringIterator.hasNext(); // return True

Constraints:

  • 1 <= compressedString.length <= 1000
  • compressedString consists of lower-case an upper-case English letters and digits.
  • The number of a single character repetitions in compressedString is in the range [1, 10^9]
  • At most 100 calls will be made to next and hasNext.

Solution

Method 1 – Two Pointers and Parsing

Intuition

We want to efficiently iterate through a compressed string like “a2b3” (which means “aabbb”) without decompressing the whole string. We can parse the string on the fly, keeping track of the current character and how many times it should be returned.

Approach

  1. Use two pointers: one to track the current position in the compressed string, and another to track the count of the current character.
  2. On initialization, parse the first character and its count.
  3. For next(), if the current count is zero, move to the next character and parse its count.
  4. For hasNext(), check if there are any characters left to return.
  5. Handle edge cases where the count is large or the string ends.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class StringIterator {
    string s;
    int i = 0, cnt = 0;
    char ch = ' ';
public:
    StringIterator(string compressedString) : s(compressedString) {}
    char next() {
        if (!hasNext()) return ' ';
        if (cnt == 0) {
            ch = s[i++];
            int n = 0;
            while (i < s.size() && isdigit(s[i])) n = n * 10 + (s[i++] - '0');
            cnt = n;
        }
        cnt--;
        return ch;
    }
    bool hasNext() {
        return cnt > 0 || i < s.size();
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

type StringIterator struct {
    s   string
    i   int
    cnt int
    ch  byte
}

func Constructor(compressedString string) StringIterator {
    return StringIterator{s: compressedString}
}

func (it *StringIterator) Next() byte {
    if !it.HasNext() {
        return ' '
    }
    if it.cnt == 0 {
        it.ch = it.s[it.i]
        it.i++
        n := 0
        for it.i < len(it.s) && it.s[it.i] >= '0' && it.s[it.i] <= '9' {
            n = n*10 + int(it.s[it.i]-'0')
            it.i++
        }
        it.cnt = n
    }
    it.cnt--
    return it.ch
}

func (it *StringIterator) HasNext() bool {
    return it.cnt > 0 || it.i < len(it.s)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

public class StringIterator {
    private String s;
    private int i = 0, cnt = 0;
    private char ch = ' ';
    public StringIterator(String compressedString) {
        s = compressedString;
    }
    public char next() {
        if (!hasNext()) return ' ';
        if (cnt == 0) {
            ch = s.charAt(i++);
            int n = 0;
            while (i < s.length() && Character.isDigit(s.charAt(i))) {
                n = n * 10 + (s.charAt(i++) - '0');
            }
            cnt = n;
        }
        cnt--;
        return ch;
    }
    public boolean hasNext() {
        return cnt > 0 || i < s.length();
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class StringIterator(compressedString: String) {
    private val s = compressedString
    private var i = 0
    private var cnt = 0
    private var ch = ' '
    fun next(): Char {
        if (!hasNext()) return ' '
        if (cnt == 0) {
            ch = s[i++]
            var n = 0
            while (i < s.length && s[i].isDigit()) {
                n = n * 10 + (s[i++] - '0')
            }
            cnt = n
        }
        cnt--
        return ch
    }
    fun hasNext(): Boolean {
        return cnt > 0 || i < s.length
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class StringIterator:
    def __init__(self, compressedString: str):
        self.s = compressedString
        self.i = 0
        self.cnt = 0
        self.ch = ' '
    def next(self) -> str:
        if not self.hasNext():
            return ' '
        if self.cnt == 0:
            self.ch = self.s[self.i]
            self.i += 1
            n = 0
            while self.i < len(self.s) and self.s[self.i].isdigit():
                n = n * 10 + int(self.s[self.i])
                self.i += 1
            self.cnt = n
        self.cnt -= 1
        return self.ch
    def hasNext(self) -> bool:
        return self.cnt > 0 or self.i < len(self.s)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

struct StringIterator {
    s: Vec<char>,
    i: usize,
    cnt: usize,
    ch: char,
}

impl StringIterator {
    fn new(compressed_string: String) -> Self {
        Self { s: compressed_string.chars().collect(), i: 0, cnt: 0, ch: ' ' }
    }
    fn next(&mut self) -> char {
        if !self.has_next() { return ' '; }
        if self.cnt == 0 {
            self.ch = self.s[self.i];
            self.i += 1;
            let mut n = 0;
            while self.i < self.s.len() && self.s[self.i].is_ascii_digit() {
                n = n * 10 + (self.s[self.i] as u8 - b'0') as usize;
                self.i += 1;
            }
            self.cnt = n;
        }
        self.cnt -= 1;
        self.ch
    }
    fn has_next(&self) -> bool {
        self.cnt > 0 || self.i < self.s.len()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class StringIterator {
    private s: string;
    private i = 0;
    private cnt = 0;
    private ch = ' ';
    constructor(compressedString: string) {
        this.s = compressedString;
    }
    next(): string {
        if (!this.hasNext()) return ' ';
        if (this.cnt === 0) {
            this.ch = this.s[this.i++];
            let n = 0;
            while (this.i < this.s.length && /\d/.test(this.s[this.i])) {
                n = n * 10 + Number(this.s[this.i++]);
            }
            this.cnt = n;
        }
        this.cnt--;
        return this.ch;
    }
    hasNext(): boolean {
        return this.cnt > 0 || this.i < this.s.length;
    }
}

Complexity

  • ⏰ Time complexity: O(1) per operation. Each next and hasNext call does a constant amount of work, since parsing the number is only done when moving to a new character, and the number of such moves is limited by the number of operations (≤ 100).
  • 🧺 Space complexity: O(1). Only a few variables are used, and we do not store the decompressed string.