1286. Iterator for Combination

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.

Analysis

When seeing combination problem, we can think of bit manipulation (0 represents not choose and 1 represents choose).

Take an example

   Num             bit_rep           no_of_set_bit       a   b   c              hold_set
    1               0 0 1                 1              0   0   1              nothing   <= because combinationLength != no_of_set_bit
    2               0 1 0                 1              0   1   0              same case like upper one
    3               0 1 1                 2              0   1   1              "bc" <= combinationLength ==no_of
    4               1 0 0                 1              1   0   0              nothing
    5               1 0 1                 2              1   0   1               "ac"
    6               1 1 0                 2              1   1   0               "ab"
    7               1 1 1                 3              1   1   1              nothing <= because combinationLength != no_of_set_bit

    return that set in lexi order ["ab","ac","bc"]

Code

class CombinationIterator {
public:
    int len, mask;
    string s;
    CombinationIterator(string characters, int combinationLength) {
        s = characters;
        len = combinationLength;
        mask = (1 << characters.length()) - 1;
    }

    string next() {
        // step 1: make sure # of bits inside the mask == len
        while(mask && __builtin_popcount(mask) != len) mask--;
        string out;
        // step 2: check each character's location in mask
        for(int i = 0; i < s.length(); i++) {
            if (mask & (1 << (s.length() - i - 1))) // chosen
                out += s[i];
        }
        // step 3: update mask to next one
        mask--; 
        return out;
    }

    bool hasNext() {
        // step 1: try to find next valid mask
        while(mask && __builtin_popcount(mask) != len) mask--;
        // step 2: see if is found or not
        if (!mask)
            return false;
        return true;
    }

};

/**
 * Your CombinationIterator object will be instantiated and called as such:
 * CombinationIterator* obj = new CombinationIterator(characters, combinationLength);
 * string param_1 = obj->next();
 * bool param_2 = obj->hasNext();
 */

---

Last update: March 31, 2022