<p>Design the <code>CombinationIterator</code> class:</p>

<ul>
	<li><code>CombinationIterator(string characters, int combinationLength)</code> Initializes the object with a string <code>characters</code> of <strong>sorted distinct</strong> lowercase English letters and a number <code>combinationLength</code> as arguments.</li>
	<li><code>next()</code> Returns the next combination of length <code>combinationLength</code> in <strong>lexicographical order</strong>.</li>
	<li><code>hasNext()</code> Returns <code>true</code> if and only if there exists a next combination.</li>
</ul>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input</strong>
[&quot;CombinationIterator&quot;, &quot;next&quot;, &quot;hasNext&quot;, &quot;next&quot;, &quot;hasNext&quot;, &quot;next&quot;, &quot;hasNext&quot;]
[[&quot;abc&quot;, 2], [], [], [], [], [], []]
<strong>Output</strong>
[null, &quot;ab&quot;, true, &quot;ac&quot;, true, &quot;bc&quot;, false]

<strong>Explanation</strong>
CombinationIterator itr = new CombinationIterator(&quot;abc&quot;, 2);
itr.next();    // return &quot;ab&quot;
itr.hasNext(); // return True
itr.next();    // return &quot;ac&quot;
itr.hasNext(); // return True
itr.next();    // return &quot;bc&quot;
itr.hasNext(); // return False
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= combinationLength &lt;= characters.length &lt;= 15</code></li>
	<li>All the characters of <code>characters</code> are <strong>unique</strong>.</li>
	<li>At most <code>10<sup>4</sup></code> calls will be made to <code>next</code> and <code>hasNext</code>.</li>
	<li>It is guaranteed that all calls of the function <code>next</code> are valid.</li>
</ul>

class CombinationIterator {
public:
    int len;
    int mask;
    string s;

    CombinationIterator(string characters, int combinationLength) {
        s = characters;
        len = combinationLength;
        mask = (1 << characters.size()) - 1;
    }
    
    string next() {
        while(mask && __builtin_popcount(mask) != len) {
            mask--;
        }
        string out;
        for(int i = 0; i < s.size(); i++) {
            if(mask & (1 << (s.size() - i - 1))) {
                out += s[i];
            }
        }
        mask--;
        return out;
    }
    
    bool hasNext() {
        while(mask && __builtin_popcount(mask) != len) {
            mask--;
        }
        if(!mask) {
            return false;
        }
        return true;
    }
};
// Hint 1
// Generate all combinations as a preprocessing.
// Hint 2
// Use bit masking to generate all the combinations.
// Idea :
// step 1 . We Need To determind The all Possiable lexicographical String With Having combinationLength
// from That Given String
// Solution Of Step 1 :
// we are Going To Create A static function OR Global Function Which take that Input string and combinationLength
// as an argument and return us A set of string having length of combinationLength in lexicographical form
// and we can genarete That all string by Using Bitmasking . How??Lets See.. fallowing
// Imp Check string length and Then Itarate Through 1 to that string length
// And consider Those Num which have set bit no == combinationLength
// then Just Take those character That lay on Set bit Possiation and Using of Those Create a String
// Lastly Put each Of string into a String set and return that set
/**
 * 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();
 */
16100