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.
1#include <vector>
2#include <string>
3#include <algorithm>
4
5class CombinationIterator {
6 std::vector<std::string> combinations;
7 size_t index;
8
9 void generate(const std::string& str, int combinationLength) {
10 std::string combination;
11 generateCombinations(str, combinationLength, 0, combination);
12 }
13
14 void generateCombinations(const std::string& str, int length, int start, std::string& combination) {
15 if (length == 0) {
16 combinations.push_back(combination);
17 return;
18 }
19 for (int i = start; i <= str.size() - length; ++i) {
20 combination.push_back(str[i]);
21 generateCombinations(str, length - 1, i + 1, combination);
22 combination.pop_back();
23 }
24 }
25
26public:
27 CombinationIterator(std::string characters, int combinationLength) : index(0) {
28 generate(characters, combinationLength);
29 }
30
31 std::string next() {
32 return combinations[index++];
33 }
34
35 bool hasNext() {
36 return index < combinations.size();
37 }
38};This C++ solution involves generating all combinations using a recursive backtracking approach. We use a helper function to manage the state and build combinations.
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.