Iterator for Combination

Problem

Design the CombinationIterator class:

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

Examples

Example 1:

**Input**
["CombinationIterator", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[["abc", 2], [], [], [], [], [], []]
**Output**
[null, "ab", true, "ac", true, "bc", false]

**Explanation**
CombinationIterator itr = new CombinationIterator("abc", 2);
itr.next();    // return "ab"
itr.hasNext(); // return True
itr.next();    // return "ac"
itr.hasNext(); // return True
itr.next();    // return "bc"
itr.hasNext(); // return False

Constraints

• 1 <= combinationLength <= characters.length <= 15
• All the characters of characters are unique.
• At most 104 calls will be made to next and hasNext.
• It is guaranteed that all calls of the function next are valid.

Solution

Method 1 – Precompute All Combinations with Backtracking

Intuition

To efficiently iterate through all possible combinations of a given length, we precompute every valid combination using backtracking. By storing these combinations in a list, we can return the next combination in lexicographical order and check if more combinations are available in constant time.

Approach

1. Use backtracking to generate all combinations of the specified length from the input string.
2. Store the combinations in a list in lexicographical order.
3. Maintain an index pointer to track the current position in the list.
4. On next(), return the combination at the current index and increment the pointer.
5. On hasNext(), check if the pointer is less than the total number of combinations.

Complexity

• ⏰ Time complexity: O(C(n, k)) for precomputing combinations, where n is the length of the string and k is the combination length. Each next() and hasNext() call is O(1).
• 🧺 Space complexity: O(C(n, k)), for storing all combinations.

Code

C++

#include <vector>
#include <string>
using namespace std;
class CombinationIterator {
    vector<string> combs;
    int idx = 0;
    void backtrack(string& chars, int k, int start, string curr) {
        if (curr.size() == k) {
            combs.push_back(curr);
            return;
        }
        for (int i = start; i < chars.size(); ++i) {
            backtrack(chars, k, i + 1, curr + chars[i]);
        }
    }
public:
    CombinationIterator(string characters, int combinationLength) {
        backtrack(characters, combinationLength, 0, "");
    }
    string next() {
        return combs[idx++];
    }
    bool hasNext() {
        return idx < combs.size();
    }
};

Java

import java.util.*;
class CombinationIterator {
    private final List<String> combs = new ArrayList<>();
    private int idx = 0;
    public CombinationIterator(String characters, int combinationLength) {
        backtrack(characters, combinationLength, 0, "");
    }
    private void backtrack(String chars, int k, int start, String curr) {
        if (curr.length() == k) {
            combs.add(curr);
            return;
        }
        for (int i = start; i < chars.length(); i++) {
            backtrack(chars, k, i + 1, curr + chars.charAt(i));
        }
    }
    public String next() {
        return combs.get(idx++);
    }
    public boolean hasNext() {
        return idx < combs.size();
    }
}

Python

class CombinationIterator:
    def __init__(self, characters: str, combinationLength: int) -> None:
        self.combs: list[str] = []
        self.idx: int = 0
        self._backtrack(characters, combinationLength, 0, "")
    def _backtrack(self, chars: str, k: int, start: int, curr: str) -> None:
        if len(curr) == k:
            self.combs.append(curr)
            return
        for i in range(start, len(chars)):
            self._backtrack(chars, k, i + 1, curr + chars[i])
    def next(self) -> str:
        ans = self.combs[self.idx]
        self.idx += 1
        return ans
    def hasNext(self) -> bool:
        return self.idx < len(self.combs)

Time complexity - O(2^N) where N is number of chars in string.

Method 2 – Bitmasking with Priority Queue

Intuition

For a string of length n, there are $2^n$ possible subsets. Each subset can be represented by a bitmask, where each bit indicates whether a character is included. To generate all combinations of a specific length k, we iterate through all bitmasks and select those with exactly k bits set. Since bitmasking does not guarantee lexicographical order, we use a priority queue (min-heap) to store and retrieve combinations in order.

Approach

1. Iterate through all bitmasks from 0 to $2^n - 1$.
2. For each bitmask, if the number of set bits equals k, construct the corresponding combination string.
3. Add each valid combination to a priority queue to maintain lexicographical order.
4. On next(), poll the next combination from the queue.
5. On hasNext(), check if the queue is not empty.

Complexity

• ⏰ Time complexity: O(2^n) for generating all bitmasks, and $O(C(n, k) \log C(n, k))$ for maintaining the priority queue. Each next() and hasNext() call is O(1).
• 🧺 Space complexity: O(C(n, k)), for storing all valid combinations in the queue.

Code

Java

import java.util.*;
class CombinationIterator {
    private Queue<String> pq;
    public CombinationIterator(String str, int combinationLength) {
        pq = new PriorityQueue<>();
        int n = str.length();
        for (int mask = 0; mask < (1 << n); mask++) {
            if (Integer.bitCount(mask) == combinationLength) {
                StringBuilder sb = new StringBuilder();
                for (int j = 0; j < n; j++) {
                    if ((mask & (1 << j)) > 0) {
                        sb.append(str.charAt(j));
                    }
                }
                pq.offer(sb.toString());
            }
        }
    }
    public String next() {
        return pq.poll();
    }
    public boolean hasNext() {
        return !pq.isEmpty();
    }
}

C++

#include <queue>
#include <string>
#include <vector>
using namespace std;
class CombinationIterator {
    priority_queue<string, vector<string>, greater<string>> pq;
public:
    CombinationIterator(string str, int combinationLength) {
        int n = str.size();
        for (int mask = 0; mask < (1 << n); ++mask) {
            if (__builtin_popcount(mask) == combinationLength) {
                string comb;
                for (int j = 0; j < n; ++j) {
                    if (mask & (1 << j)) comb += str[j];
                }
                pq.push(comb);
            }
        }
    }
    string next() {
        string ans = pq.top(); pq.pop();
        return ans;
    }
    bool hasNext() {
        return !pq.empty();
    }
};

Python

import heapq
class CombinationIterator:
    def __init__(self, characters: str, combinationLength: int) -> None:
        self.pq: list[str] = []
        n = len(characters)
        for mask in range(1 << n):
            if bin(mask).count('1') == combinationLength:
                comb = ''.join(characters[j] for j in range(n) if (mask & (1 << j)))
                heapq.heappush(self.pq, comb)
    def next(self) -> str:
        return heapq.heappop(self.pq)
    def hasNext(self) -> bool:
        return len(self.pq) > 0