Design Compressed String Iterator - Practice Coding Problems

Design Compressed String Iterator - 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:

StringIterator(String compressedString): Initializes the object with a compressed string.
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.

Input & Output

Example 1 — Basic Compression

$ Input: compressedString = "L1e2t1C4o1d3e1"

› Output: LeetCCCCoddde

💡 Note: L appears 1 time, e appears 2 times, t appears 1 time, C appears 4 times, o appears 1 time, d appears 3 times, e appears 1 time

Example 2 — Single Character

$ Input: compressedString = "x5"

› Output: xxxxx

💡 Note: Character x appears 5 times consecutively

Example 3 — Mixed Case

$ Input: compressedString = "A2b3C1"

› Output: AAbbbC

💡 Note: A appears 2 times, b appears 3 times, C appears 1 time

Constraints

1 ≤ compressedString.length ≤ 1000
compressedString consists of lowercase and uppercase English letters and digits
The number after each character is in the range [1, 999]

Visualization

Tap to expand

Understanding the Visualization

Input Format

Compressed string with character followed by count

Iterator Design

Track current character and remaining count

Output Generation

Return characters one by one until exhausted

Key Takeaway

🎯 Key Insight: Parse compressed format into character-count pairs and track current state dynamically, avoiding memory waste from full expansion.

Asked in

G Google 45 a Amazon 38 M Microsoft 32 f Facebook 25

The key insight is to avoid expanding the entire string upfront. Instead, parse the compressed format into character-count pairs and track the current position. The optimized approach uses O(k) space for k character groups instead of O(n) for n total characters. Time: O(k + m), Space: O(k).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Expand All Characters	O(n)	O(n)	Expand the entire compressed string into individual characters upfront
Optimized - Parse on Demand	O(k + m)	O(k)	Parse character-count pairs only when needed, track current character and remaining count

Brute Force - Expand All Characters — Algorithm Steps

Parse compressed string to extract character-count pairs
Expand each character according to its count
Store all characters in a list
Use index pointer to track current position

Visualization

Tap to expand

Step-by-Step Walkthrough

Parse

Extract character-count pairs from compressed string

Expand

Create array with all characters repeated

Iterate

Use index to traverse the expanded array

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

typedef struct {
    char* chars;
    int size;
    int index;
} StringIterator;

StringIterator* createStringIterator(char* compressedString) {
    StringIterator* iterator = (StringIterator*)malloc(sizeof(StringIterator));
    iterator->chars = (char*)malloc(10000 * sizeof(char));
    iterator->size = 0;
    iterator->index = 0;
    
    int i = 0;
    int len = strlen(compressedString);
    while (i < len) {
        char ch = compressedString[i];
        i++;
        char numStr[10] = "";
        int numIdx = 0;
        while (i < len && isdigit(compressedString[i])) {
            numStr[numIdx++] = compressedString[i];
            i++;
        }
        numStr[numIdx] = '\0';
        int count = atoi(numStr);
        for (int j = 0; j < count; j++) {
            iterator->chars[iterator->size++] = ch;
        }
    }
    return iterator;
}

char next(StringIterator* iterator) {
    if (iterator->index < iterator->size) {
        return iterator->chars[iterator->index++];
    }
    return ' ';
}

int hasNext(StringIterator* iterator) {
    return iterator->index < iterator->size;
}

char* solution(char* compressedString) {
    StringIterator* iterator = createStringIterator(compressedString);
    char* result = (char*)malloc(10000 * sizeof(char));
    int idx = 0;
    while (hasNext(iterator)) {
        result[idx++] = next(iterator);
    }
    result[idx] = '\0';
    free(iterator->chars);
    free(iterator);
    return result;
}

int main() {
    char compressedString[1000];
    fgets(compressedString, sizeof(compressedString), stdin);
    compressedString[strcspn(compressedString, "\n")] = 0;
    char* result = solution(compressedString);
    printf("%s\n", result);
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Where n is the total length of uncompressed string - we iterate through each character once

✓ Linear Growth

Space Complexity

O(n)

Store all n characters of the expanded string in memory

⚡ Linearithmic Space

34.5K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Expand All Characters — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler