Sponsored
Sponsored
In this approach, we precompute all the combinations of the given string of a specified length. This allows us to provide the next combination in constant time by just iterating over the precomputed list. For this, we can use recursion or libraries to generate combinations initially and store them in an internal data structure.
To find all combinations of a particular length, you can use backtracking or an iterative process that resembles a binary-like increase in combinations selection.
Time Complexity: O(n!) for precomputation, O(1) for next and hasNext.
Space Complexity: O(n!) due to storage of combinations.
1from itertools import combinations
2
3class CombinationIterator:
4 def __init__(self, characters: str, combinationLength: int):
5 self.combinations = list(combinations(characters, combinationLength))
6 self.index = 0
7
8 def next(self) -> str:
9 comb = self.combinations[self.index]
10 self.index += 1
11 return ''.join(comb)
12
13 def hasNext(self) -> bool:
14 return self.index < len(self.combinations)This Python solution uses the itertools.combinations library to generate all the combinations of the given length at the initialization stage. Whenever next() is called, it returns the current combination and advances the index.
Instead of generating all combinations at once, we can generate them on the fly when next() is called. This approach uses bit manipulation to generate the combination efficiently by representing each combination as a bitmask. However, this requires understanding how to generate valid combinations incrementally with proper bit manipulation.
Time Complexity: O(1) for next and hasNext, average complexity due to combination generation logic.
Space Complexity: O(combinationLength), the storage used for the indices.
1public class CombinationIterator {
2 private string characters;
3 private int combinationLength;
4 private int[] indices;
private bool hasCombination;
public CombinationIterator(string characters, int combinationLength) {
this.characters = characters;
this.combinationLength = combinationLength;
this.indices = new int[combinationLength];
for (int i = 0; i < combinationLength; i++) {
indices[i] = i;
}
hasCombination = true;
}
public string Next() {
if (!hasCombination) return null;
char[] combination = new char[combinationLength];
for (int i = 0; i < combinationLength; i++) {
combination[i] = characters[indices[i]];
}
getNextIndices();
return new string(combination);
}
private void getNextIndices() {
int n = characters.Length;
for (int i = combinationLength - 1; i >= 0; i--) {
if (indices[i] != i + n - combinationLength) {
indices[i]++;
for (int j = i + 1; j < combinationLength; j++) {
indices[j] = indices[j - 1] + 1;
}
return;
}
}
hasCombination = false;
}
public bool HasNext() {
return hasCombination;
}
}This C# solution uses an indices array to represent the current combination. It simulates the generation of combinations by modifying the indices array with each call to next(). When there is a valid combination, the indices are updated to represent the next viable combination.