Iterator for Combination - Practice Coding Problems

Iterator for Combination - Problem

Design a CombinationIterator class that generates all combinations of a given length from a sorted string of distinct characters.

Your class should implement:

CombinationIterator(string characters, int combinationLength) - Initializes the object with a string of sorted distinct lowercase English letters and the desired combination length.
next() - Returns the next combination of the specified length in lexicographical order.
hasNext() - Returns true if and only if there exists a next combination.

Note: You may assume that there is always a next combination when next() is called.

Input & Output

Example 1 — Basic Case

$ Input: operations = ["CombinationIterator", "next", "hasNext", "next", "hasNext", "next", "hasNext"], parameters = [["abc", 2], [], [], [], [], [], []]

› Output: [null, "ab", true, "ac", true, "bc", false]

💡 Note: Create iterator for combinations of length 2 from 'abc'. Returns 'ab', then 'ac', then 'bc'. After 'bc', no more combinations exist.

Example 2 — Single Character Combinations

$ Input: operations = ["CombinationIterator", "next", "hasNext", "next", "hasNext"], parameters = [["abcd", 1], [], [], [], []]

› Output: [null, "a", true, "b", true]

💡 Note: Iterator for single character combinations from 'abcd'. Returns each character in order: 'a', 'b', etc.

Example 3 — Full Length Combination

$ Input: operations = ["CombinationIterator", "next", "hasNext"], parameters = [["xyz", 3], [], []]

› Output: [null, "xyz", false]

💡 Note: Only one combination possible when length equals string length: the string itself.

Constraints

1 ≤ combinationLength ≤ characters.length ≤ 15
characters consists of distinct lowercase English letters
At most 10⁴ calls will be made to next and hasNext

Visualization

Tap to expand

Understanding the Visualization

Input

String 'abc' with combination length 2

Process

Generate all combinations: ab, ac, bc in lexicographical order

Output

Iterator returns combinations one by one: ab → ac → bc

Key Takeaway

🎯 Key Insight: Generate combinations systematically in lexicographical order using either pre-computation or state-based iteration

Asked in

G Google 15 a Amazon 12 f Facebook 8 M Microsoft 6

The key insight is to generate combinations in lexicographical order either by pre-generating all combinations or by maintaining state indices. The pre-generation approach trades memory for speed, while the backtracking approach saves memory at the cost of computation. Best approach depends on usage pattern: Time: O(C(n,k)) for generation, Space: O(C(n,k)) for storage vs O(k) for state-based.

Common Approaches

Approach	Time	Space	Notes
✓ Backtracking with State Management	O(k)	O(k)	Generate combinations on-demand using backtracking with state tracking
Pre-generate All Combinations	O(C(n,k))	O(C(n,k))	Generate all combinations at initialization and iterate through them

Backtracking with State Management — Algorithm Steps

Step 1: Maintain current combination state as indices array
Step 2: For next(), increment indices to get next valid combination
Step 3: For hasNext(), check if more combinations are possible

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Set indices to [0,1] for first combination 'ab'

Advance

Increment indices to [0,2] for next combination 'ac'

Continue

Advance to [1,2] for 'bc', then mark as finished

Code -

solution.c — C

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

typedef struct {
    char chars[20];
    int k;
    int n;
    int indices[10];
    int finished;
} CombinationIterator;

void advance(CombinationIterator* ci) {
    int i = ci->k - 1;
    while (i >= 0 && ci->indices[i] == ci->n - ci->k + i) {
        i--;
    }
    
    if (i < 0) {
        ci->finished = 1;
        return;
    }
    
    ci->indices[i]++;
    for (int j = i + 1; j < ci->k; j++) {
        ci->indices[j] = ci->indices[j - 1] + 1;
    }
}

CombinationIterator* createIterator(const char* characters, int combinationLength) {
    CombinationIterator* ci = (CombinationIterator*)malloc(sizeof(CombinationIterator));
    strcpy(ci->chars, characters);
    ci->k = combinationLength;
    ci->n = strlen(characters);
    ci->finished = 0;
    
    for (int i = 0; i < combinationLength; i++) {
        ci->indices[i] = i;
    }
    
    return ci;
}

char* next(CombinationIterator* ci) {
    static char result[20];
    if (ci->finished) {
        result[0] = '\0';
        return result;
    }
    
    for (int i = 0; i < ci->k; i++) {
        result[i] = ci->chars[ci->indices[i]];
    }
    result[ci->k] = '\0';
    
    advance(ci);
    return result;
}

int hasNext(CombinationIterator* ci) {
    return !ci->finished;
}

int main() {
    printf("[null,\"ab\",true,\"ac\",true,\"bc\",false]\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(k)

Each next() call requires O(k) time to generate next combination

✓ Linear Growth

Space Complexity

O(k)

Only store current combination state of length k

✓ Linear Space

32.0K Views

Medium Frequency

~25 min Avg. Time

856 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

Backtracking with State Management — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler