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:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
**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#
Use backtracking to generate all combinations of the specified length from the input string.
Store the combinations in a list in lexicographical order.
Maintain an index pointer to track the current position in the list.
On next(), return the combination at the current index and increment the pointer.
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#
Cpp
Java
Python
Time Complexity - O(2^n) Where N Is Number of Chars in String.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#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();
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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 ();
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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)
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#
Iterate through all bitmasks from 0 to $2^n - 1$.
For each bitmask, if the number of set bits equals k, construct the corresponding combination string.
Add each valid combination to a priority queue to maintain lexicographical order.
On next(), poll the next combination from the queue.
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
Cpp
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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 ();
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#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();
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
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