Iterator for Combination Problem

Design an Iterator class, which has:

• A constructor that takes a string characters of sorted distinct lowercase English letters and a number combinationLength as arguments.
• A function next() that returns the next combination of length combinationLength in lexicographical order.
• A function hasNext() that returns True if and only if there exists a next combination.

Example:

CombinationIterator iterator = new CombinationIterator("abc", 2); // creates the iterator.iterator.next(); // returns "ab"
iterator.hasNext(); // returns true
iterator.next(); // returns "ac"
iterator.hasNext(); // returns true
iterator.next(); // returns "bc"
iterator.hasNext(); // returns false

Constraints:

• 1 <= combinationLength <= characters.length <= 15
• There will be at most 10^4 function calls per test.
• It’s guaranteed that all calls of the function next are valid.

Solution

For creating all the possible combinations, I have done first of all, all the combinations for Characters.Length bits (bitsCombinations).

The generation of the bits is set to first generate the true values on purpose, to get the combinations ordered.

When having all the possible combinations in bitsCombinations, we have to leave the ones that have CombinationLength of number ones, and remove the other ones.

After this, we will have all the possible combination we can make, in a list of booleans, meaning which character in Characters needs to be taken for the combination.

I have added currentWordIndex to check the index of the words in which we are. To know if HasNext() is true, we should check if currentWordIndex is smaller than the wordsCombinations.

To get the Next() value, we will just return the value of wordsCombinations in currentWordIndex and increment currentWordIndex by one.

Here you can see the performance of my solution (keep in mind that Runtime can vary depending on the server):

You can follow me on LinkedIn.