604. Design Compressed String Iterator
Problem Description
The task is to design a data structure that can efficiently iterate through a compressed string. The compressed format represents a string where each distinct character is followed by an integer that indicates the number of times the character appears consecutively in the original, uncompressed string. For example, the compressed string "a2b1c5" represents "aabc". The class StringIterator
should have the following functionalities:
next()
: This function should return the next character in the uncompressed version of the string. If there are no more characters to return, it should return a white space character.hasNext()
: This function should tell us whether there are more characters that can be uncompressed from the string, returningtrue
if more characters exist andfalse
otherwise.
Intuition
The fundamental intuition behind the solution is to maintain a data structure that can easily track the current character and the number of times it still needs to be returned by the next()
function.
To solve this, we can use a list of pairs, where each pair consists of a character and a number indicating how many times that character should be repeated in the uncompressed string.
Here's the thinking process for designing the StringIterator
:
-
Initialization: We parse the compressed string to fill our list with pairs of characters and their respective counts.
-
Next: Each call to
next()
should return the current character and decrement the count. If the count reaches zero, that means we have fully uncompressed that character, and we need to move on to the next character. -
HasNext: To determine whether more characters need to be iterated upon, we check if the current position is less than the length of the list and the count at that position is greater than zero.
By keeping track of our position within the list, we can efficiently return the correct character for each next()
call until all characters are fully uncompressed.
Solution Approach
The Reference Solution Approach you provided outlines a way to implement the StringIterator
class using the logic previously described. Here's how the solution is implemented step-by-step:
-
Initialization in
__init__
:- We parse the compressed string character by character.
- A pointer
i
iterates over the string. Wheni
points to a letter, we initialize a counterx
to 0 and start building the count by moving to the next character and continue until we reach a character that is not a digit. - We multiply
x
by 10 and add the integer value of the current digit tox
with each consecutive digit to build the count for the current letter correctly. - This count along with the character is stored as a pair (a list with two elements) in the list
self.d
which represents the decompressed format of the given compressed string.
-
next
Method:- First, we check if there is a next character by calling the
hasNext
method. If not, we return a space character as per the problem statement. - If
hasNext
is true, we retrieve the current character fromself.d
using our current positionself.p
. - We then decrement the count (which is the second element of the pair) for that character at
self.p
as we have returned this character once. - If the count becomes zero, it means we have exhausted this character; hence, we increment
self.p
to move to the next character. - We return the character that was next in line.
- First, we check if there is a next character by calling the
-
hasNext
Method:- We check if the current position
self.p
is less than the length ofself.d
which means there are characters left to be returned. - Additionally, we ensure that the count of the current letter at position
self.p
is greater than zero, indicating that the current character is still available to be returned by thenext
method. - The method returns
True
if both conditions are met, andFalse
otherwise.
- We check if the current position
This approach efficiently solves the problem using a linear scan to parse the compressed string and then providing O(1)
operations to return the next character and check for remaining characters.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider a small example to illustrate the solution approach using the class StringIterator
for the compressed string "a2b1c5"
. This represents the uncompressed string "aabccccc"
.
-
Initialization: First, we initialize our
StringIterator
with the compressed string"a2b1c5"
. During the initialization:- The constructor (
__init__
) parses the string and fillsself.d
with the list of pairs:[('a', 2), ('b', 1), ('c', 5)]
. - The current pointer
self.p
is set to 0 to start from the first character pair.
- The constructor (
-
First
next
Call: We callnext()
for the first time.hasNext()
is true becauseself.p
is 0, which is less than the length ofself.d
(which is 3), and the count for'a'
at this position is 2 (greater than zero).next()
returns'a'
and decrements the count of'a'
in the pair to 1.
-
Second
next
Call: We callnext()
again.hasNext()
is still true for the same reasons as before.next()
returns'a'
again, as there's still 1 count left for'a'
, and decrements the count of'a'
to 0.
-
Third
next
Call: We callnext()
once more.hasNext()
is again true since nowself.p
is referring to the next character pair,('b', 1)
, after incrementingself.p
since'a'
count reached 0.next()
returns'b'
and the count of'b'
in the pair becomes 0, andself.p
is incremented to point to('c', 5)
.
-
Subsequent
next
Calls: If we continue to callnext()
, it would return'c'
five times, decrementing the count each time. After this,self.p
would be 3, which is the length ofself.d
, and no character would be left. -
Final
next
Call: After exhausting all characters, when we callnext()
,hasNext()
would return false sinceself.p
is equal to the length ofself.d
. As per the requirement,next()
would return a space character ' -
Calling
hasNext
: At any point, we can callhasNext()
to check if there are more characters to be uncompressed. This would returntrue
until thenext
method has been called enough times to exhaust all the characters as per their counts inself.d
.
The solution implemented as described allows the StringIterator
to iterate through the compressed string efficiently and return uncompressed characters one at a time.
Solution Implementation
1class StringIterator:
2 def __init__(self, compressed_string: str):
3 self.decoded = [] # List to store the characters and their counts
4 self.pointer = 0 # Pointer to track the current character
5 length = len(compressed_string) # Length of the compressed string
6 index = 0
7
8 # Iterate over the compressed string and decode it
9 while index < length:
10 char = compressed_string[index]
11 count = 0
12 index += 1
13
14 # Extract the count for the current character
15 while index < length and compressed_string[index].isdigit():
16 count = count * 10 + int(compressed_string[index])
17 index += 1
18
19 # Append the character and its count to the decoded list
20 self.decoded.append([char, count])
21
22 def next(self) -> str:
23 # Return the next character if available
24 if not self.hasNext():
25 return ' ' # If no next character, return a space
26 current_char = self.decoded[self.pointer][0] # Get current character
27 self.decoded[self.pointer][1] -= 1 # Decrement its count
28
29 # If the current character's count hits 0, move to the next character
30 if self.decoded[self.pointer][1] == 0:
31 self.pointer += 1
32 return current_char
33
34 def hasNext(self) -> bool:
35 # Check if there is a next character available
36 return self.pointer < len(self.decoded) and self.decoded[self.pointer][1] > 0
37
38
39# Usage example:
40# string_iterator = StringIterator("a2b1")
41# print(string_iterator.next()) # Outputs: 'a'
42# print(string_iterator.hasNext()) # Outputs: True
43
1class StringIterator {
2 // Node class to store individual characters and their counts.
3 private static class Node {
4 char character;
5 int count;
6
7 Node(char character, int count) {
8 this.character = character;
9 this.count = count;
10 }
11 }
12
13 // A list to hold all the nodes derived from the compressed string.
14 private List<Node> data = new ArrayList<>();
15 // The current position in the list of nodes.
16 private int position;
17
18 // Constructor to parse the compressed string and initialize the data list.
19 public StringIterator(String compressedString) {
20 int length = compressedString.length();
21 int index = 0; // Index to iterate the compressed string.
22
23 while (index < length) {
24 // Extract the character at the current index.
25 char currentChar = compressedString.charAt(index);
26 int count = 0; // To keep track of the count of characters.
27
28 // Move to the next index and parse the digit(s) to find the count.
29 while (++index < length && Character.isDigit(compressedString.charAt(index))) {
30 count = count * 10 + (compressedString.charAt(index) - '0');
31 }
32
33 // Add the extracted character and its count to the data list as a new Node.
34 data.add(new Node(currentChar, count));
35 }
36 }
37
38 // Returns the next character in the sequence.
39 public char next() {
40 // If hasNext() returns false, return a space.
41 if (!hasNext()) {
42 return ' ';
43 }
44
45 // Get the current node based on the position and retrieve its character.
46 Node currentNode = data.get(position);
47 char resultChar = currentNode.character;
48
49 // Decrement the count of the character and move the position if count reaches 0.
50 if (--currentNode.count == 0) {
51 position++;
52 }
53
54 // Return the character.
55 return resultChar;
56 }
57
58 // Check if there are more characters to return.
59 public boolean hasNext() {
60 // hasNext is true if the current position is within the bounds of the data list
61 // and the count of the current node is greater than 0.
62 return position < data.size() && data.get(position).count > 0;
63 }
64}
65
66/**
67 * This class simulates an iterator over a string that has been compressed
68 * where characters are followed by their counts. The iterator provides the
69 * functionality to iterate over the uncompressed sequence of characters.
70 *
71 * Example usage:
72 * StringIterator iterator = new StringIterator("L1e2t1C1o1d1e1");
73 * char c = iterator.next(); // returns 'L'
74 * boolean hasNext = iterator.hasNext(); // returns true since there are more characters
75 */
76
1#include <string>
2#include <vector>
3#include <utility>
4using namespace std;
5
6class StringIterator {
7public:
8 // Constructor that initializes the object with the compressed string
9 StringIterator(string compressedString) {
10 int length = compressedString.length(); // Get the length of the compressed string
11 int index = 0; // Index to track our position in the string
12
13 // Loop through the compressed string
14 while (index < length) {
15 char letter = compressedString[index]; // Current character to be decoded
16 int count = 0; // Count of how many times the current character is repeated
17
18 // Increase index and calculate the count
19 while (++index < length && isdigit(compressedString[index])) {
20 count = count * 10 + (compressedString[index] - '0');
21 }
22
23 // Save the character and its count to the deque
24 data.push_back({letter, count});
25 }
26 }
27
28 // Returns the next character in the uncompressed version of the string or ' ' if there is none
29 char next() {
30 if (!hasNext()) {
31 return ' '; // If there are no more characters, return a space
32 }
33
34 // Get the current character to return
35 char result = data[position].first;
36
37 // Decrease the count of how many times this character should be repeated
38 if (--data[position].second == 0) {
39 ++position; // Move to the next character when current is exhausted
40 }
41
42 return result;
43 }
44
45 // Check if there is any character left to return
46 bool hasNext() {
47 return position < data.size() && data[position].second > 0;
48 }
49
50private:
51 // A deque to store pairs of characters and their respective counts
52 vector<pair<char, int>> data;
53
54 // Position variable to keep track of the current character
55 int position = 0;
56};
57
58/**
59 * Your StringIterator object will be instantiated and called as such:
60 * StringIterator* obj = new StringIterator(compressedString);
61 * char param_1 = obj->next();
62 * bool param_2 = obj->hasNext();
63 */
64
1// Define a data type for the pair of character and its count
2type CharCountPair = {
3 character: string;
4 count: number;
5};
6
7// Create an array to store CharCountPair
8let data: CharCountPair[] = [];
9
10// Position variable to keep track of the current character pair index
11let position: number = 0;
12
13// Function to initialize the object with the compressed string
14function initialize(compressedString: string): void {
15 const length = compressedString.length; // Get the length of the compressed string
16 let index = 0; // Index to track our position in the string
17
18 // Loop through the compressed string
19 while (index < length) {
20 const letter = compressedString[index]; // Current character to be decoded
21 let count = 0; // Count of how many times the current character is repeated
22
23 // Increase index and calculate the count
24 while (++index < length && isDigit(compressedString[index])) {
25 count = count * 10 + (parseInt(compressedString[index]));
26 }
27
28 // Save the character and its count to the data array
29 data.push({character: letter, count: count});
30 }
31}
32
33// Utility function to check if a character is a digit
34function isDigit(char: string): boolean {
35 return !isNaN(parseInt(char, 10));
36}
37
38// Function to return the next character in the uncompressed version of the string or ' ' if there is none
39function next(): string {
40 if (!hasNext()) {
41 return ' '; // If there are no more characters, return a space
42 }
43
44 // Get the current character pair
45 const currentPair = data[position];
46
47 // Get the current character to return
48 const result = currentPair.character;
49
50 // Decrease the count of how many times this character should be repeated
51 if (--currentPair.count === 0) {
52 ++position; // Move to the next character pair when current is exhausted
53 }
54
55 return result;
56}
57
58// Function to check if there is any character left to return
59function hasNext(): boolean {
60 return position < data.length && data[position]?.count > 0;
61}
62
63// Examples of usage:
64// initialize("x2y4"); // Example initialization with compressed string "x2y4"
65// console.log(next()); // Returns the next character 'x'
66// console.log(hasNext()); // Returns true if there are characters remaining, false otherwise
67
Time and Space Complexity
Time Complexity
-
__init__
function: This function has a while loop that iterates over the entire length of the input stringcompressedString
. Within this loop, there is a nested while loop that processes the digits following a letter, which can at most beO(m)
wherem
is the number of digits following a letter. However, since each character is only visited once, the overall time complexity of__init__
isO(n)
wheren
is the length ofcompressedString
. -
next
function: Thenext
method decreases the count of the current character and moves the pointerself.p
forward if needed. These operations are done in constant time, hence the time complexity of thenext
function isO(1)
. -
hasNext
function: This function checks if there is a next element in the iterator, which is done by simply comparing the current pointerself.p
with the length of the listself.d
. This is a constant time operation, so the time complexity ofhasNext
isO(1)
.
Space Complexity
-
__init__
function: Since we are storing each character and its count in a listself.d
, and there can be at mostn/2
different characters if we alternate between characters and single digits, the space complexity isO(n)
. -
next
andhasNext
functions: These functions do not use any additional space that scales with the input size, so their space complexity isO(1)
.
Combining the above, the space complexity for the entire StringIterator
class is dominated by the __init__
function, which is O(n)
.
Learn more about how to find time and space complexity quickly using problem constraints.
What's the output of running the following function using the following tree as input?
1def serialize(root):
2 res = []
3 def dfs(root):
4 if not root:
5 res.append('x')
6 return
7 res.append(root.val)
8 dfs(root.left)
9 dfs(root.right)
10 dfs(root)
11 return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4 StringJoiner res = new StringJoiner(" ");
5 serializeDFS(root, res);
6 return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10 if (root == null) {
11 result.add("x");
12 return;
13 }
14 result.add(Integer.toString(root.val));
15 serializeDFS(root.left, result);
16 serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2 let res = [];
3 serialize_dfs(root, res);
4 return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8 if (!root) {
9 res.push("x");
10 return;
11 }
12 res.push(root.val);
13 serialize_dfs(root.left, res);
14 serialize_dfs(root.right, res);
15}
16
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Don’t Miss This!