Design Compressed String Iterator
EasyUpdated: Aug 2, 2025
Practice on:
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 returnsfalse.
Examples
Example 1:
**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 <= 1000compressedStringconsists of lower-case an upper-case English letters and digits.- The number of a single character repetitions in
compressedStringis in the range[1, 10^9] - At most
100calls will be made tonextandhasNext.
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
- Use two pointers: one to track the current position in the compressed string, and another to track the count of the current character.
- On initialization, parse the first character and its count.
- For
next(), if the current count is zero, move to the next character and parse its count. - For
hasNext(), check if there are any characters left to return. - Handle edge cases where the count is large or the string ends.
Code
C++
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();
}
};
Go
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)
}
Java
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();
}
}
Kotlin
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
}
}
Python
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)
Rust
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()
}
}
TypeScript
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. EachnextandhasNextcall 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.