Design Compressed String Iterator

Design Compressed String Iterator is a Easy Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Design Patterns pattern, in the Design (General/Specific) subpattern.

Problem statement

You are given a compressed string compressedString, where each group consists of a single uppercase or lowercase letter followed by a positive integer representing the number of times that letter appears consecutively in the original string. For example, the compressed string "a2b3" represents the uncompressed string "aabbb".

Design a class StringIterator that supports the following operations:

- next(): Returns the next character in the uncompressed string as a string. If there are no more characters to return, returns a single space character " ". - hasNext(): Returns true if there are more characters to be iterated, or false otherwise.

Implement the StringIterator class with the above methods to efficiently iterate through the uncompressed string without decompressing the entire string into memory.

Topics and companies

Topics: Array, String, Design, Iterator.

Reported in interviews at Google, Amazon.

How to practise Design Compressed String Iterator on Thita.ai

Starter code is provided in C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(1) amortized per next()/hasNext() call. Each character and digit in the compressed string is processed at most once, and parsing is done as needed. time and O(1) auxiliary (excluding input string). Only a few integer and character variables are used. The compressed string is stored as a member variable. space.

Open Design Compressed String Iterator in the code editor, or read the Design Compressed String Iterator editorial for a worked solution with its approach and complexity analysis.

Where Design Compressed String Iterator sits in the DSA pattern sheet

• Design Patterns pattern guide
• Design (General/Specific) subpattern
• The full DSA patterns sheet
• All coding practice problems

Problems related to Design Compressed String Iterator

Other problems that use the same Design (General/Specific) and Design Patterns techniques:

• All O`one Data Structure — Hard, same subpattern
• Design a Stack With Increment Operation — Medium, same subpattern
• Design a Text Editor — Hard, same subpattern
• Design Circular Deque — Medium, same subpattern
• Design Circular Queue — Medium, same subpattern
• Design HashMap — Easy, same subpattern