Iterator for Combination

• 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.

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

• 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.

class CombinationIterator {
    public Deque < String > combinations = new ArrayDeque < String > ();

    public CombinationIterator(String characters, int combinationLength) {
        int n = characters.length();
        int k = combinationLength;

        // generate bitmasks from 0..00 to 1..11  
        for (int bitmask = 0; bitmask < 1 << n; bitmask++) {
            // use bitmasks with k 1-bits
            if (Integer.bitCount(bitmask) == k) {
                // convert bitmask into combination
                // 111 --> "abc", 000 --> ""
                // 110 --> "ab", 101 --> "ac", 011 --> "bc"
                StringBuilder curr = new StringBuilder();
                for (int j = 0; j < n; j++) {
                    if ((bitmask & (1 << n - j - 1)) != 0) {
                        curr.append(characters.charAt(j));
                    }
                }
                combinations.push(curr.toString());
            }
        }
    }

    public String next() {
        return combinations.pop();
    }

    public boolean hasNext() {
        return (!combinations.isEmpty());
    }
}

class CombinationIterator {
    int[] nums;
    boolean has_next;
    int n, k;
    String chars;

    public CombinationIterator(String characters, int combinationLength) {
        n = characters.length();
        k = combinationLength;
        chars = characters;

        // init the first combination
        has_next = true;
        nums = new int[k];
        for (int i = 0; i < k; ++i) {
            nums[i] = i;
        }
    }

    public String next() {
        StringBuilder curr = new StringBuilder();
        for (int j: nums) {
            curr.append(chars.charAt(j));
        }

        /* Generate next combination.
            Find the first index j such that nums[j] != n - k + j.
            nums[j] == n - k + j indicates that you have no additional combination you can create with current index and have to use previous index to generate new combination.
            e.g. "abcd", "2" -> if next string is "ad"
           j is (k - 1) which in this case is 1
          nums[1] = 3 == 4 - 2 + 1 (true as "d"'s index is 3)
          nums[0] = 0 != 4 - 2 + 0 (false as "a"'s index is 0)
       */
        int j = k - 1;
        while (j >= 0 && nums[j] == n - k + j) {
            j--;
        }

        if (j >= 0) {
            nums[j]++;
            // move the next indexes right next to nums[j] here 
            // since j is not necessarily 0, so we need to subtract j from nums[j] 
            // to count for the offset. 
            //  (similar to how we have carry in addition or multiplication)
            for (int i = j + 1; i < k; i++) {
                // i - j here means spaces away from nums[j]
                //             0  + 1 - 0
                nums[i] = nums[j] + i - j;
            }
        } else {
            has_next = false;
        }

        return curr.toString();
    }

    public boolean hasNext() {
        return has_next;
    }
}

/**
 * Your CombinationIterator object will be instantiated and called as such:
 * CombinationIterator obj = new CombinationIterator(characters, combinationLength);
 * String param_1 = obj.next();
 * boolean param_2 = obj.hasNext();
 */