✅ [C++] EASY Intuitive Sol || BITMASK APPROACH || DRY RUN
Hello everyone, I hope you all are doing great!\n\nNote: Kindly Upvote  \uD83D\uDD3C if my solution helped you!\n\nWe need to create CombinationIterator class w
Hello everyone, I hope you all are doing great!\n\n*Note: Kindly Upvote  \uD83D\uDD3C if my solution helped you!*\n\nWe need to create CombinationIterator class with two functionalities : next and hasNext.\n\n**My Approach:**\n1. We will precompute all the possible strings that can exist for a `combinationLength` in lexicographical order during the time of initialization of the object of our class (can be done easily in the constructor of class).\n\n2. Now, in the constructor method of class we will use **Power Set Method**  to generate all the subsets of our character of our characters string that have length equals to the combination length.\n\n3. Then when we have generated our subset of characters string (store the characters in set to have them in lexicographical order), then create a string from that sorted subset and store the string in a set. This will ensure that we have all the strings in lexicographical order.\n\n4. I will then just use a set iterator to iterate through the set of our precomputed strings.\n\n**Dry Run:**\n```\ncharacters = "abc", combinationsLength = 2\nInput comes like this: ["next", "hasNext", "next", "hasNext", "next", "hasNext"]\n```\n\n**Initialization of object of CombinationIterator class**:\n```\nTotal subsets possible for "abc" = 2^len("abc") = 2^3 = 8\nNow bitmasks for all 8 subset are as follows:\nRemember In bitmask, indexing goes from LSB to MSB i.e. from right to left.\nFor, eg: In string, "afgh" we have \'h\' at 0th bit and \'g\' at 1th bit, and so on till \'a\' at 3rd bit.\n\n000      ->      empty string      ->      Empty set (NOT added to our combinations set)\n001      ->      "a"               ->      Length of string is 1 and combinationLength is 2, hence NOT added\n010      ->      "b"               ->      Same as above\n011      ->      "ba"              ->      Length of string = combinationsLength, hence ADDED to combinations set (In sorted order i.e. "ab")\n100      ->      "c"               ->      Length of string is 1 and combinationLength is 2, hence NOT added\n101      ->      "ca"              ->      Length of string = combinationsLength, hence ADDED to combinations set (In sorted order i.e. "ac")\n110      ->      "cb"              ->      Length of string = combinationsLength, hence ADDED to combinations set (In sorted order i.e. "bc")\n111      ->      "cba"             ->      Length of string is 3, but combinationsLength is 2 hence NOT added to combinations set\n```\n\nNow, our main set i.e. combination set and current set iterator(set pointer) looks like this:\n```\nMain set = ["ab", "ac", "bc"]\n             \uD83D\uDC46(current pointer to our set)\n```\n**1st Query: *next***\n```\nreturn "ab" and move pointer forward\nMain set = ["ab", "ac", "bc"]\n                   \uD83D\uDC46(current pointer to our set)\n```\n**2nd Query: *hasNext***\n```\nwe check that cur pointer is NOT pointing at the end of our set, hance return true\nMain set = ["ab", "ac", "bc"]\n                   \uD83D\uDC46(current pointer to our set)\n```\n**3rd Query: *next***\n```\nreturn "ac" and move pointer forward\nMain set = ["ab", "ac", "bc"]\n                         \uD83D\uDC46(current pointer to our set)\n```\n**4th Query: *hasNext***\n```\nreturn true since pointer is not pointing at the end of our set\nMain set = ["ab", "ac", "bc"]\n                         \uD83D\uDC46(current pointer to our set)\n```\n**5th Query: *next***\n```\nreturn "bc" and move the pointer forward\nMain set = ["ab", "ac", "bc"]\n                             \uD83D\uDC46(current pointer to our set) <- This is the end of set \n```\n**6th Query: *hasNext***\n```\nreturn false \nBecause our pointer is pointing at the end of set and that means we have no other strings left\n```\n\nBelow is the code for my approach mentioned above:\n```\nclass CombinationIterator {\nprivate:\n    set<string>combinations; // Our main set\n    set<string>::iterator cur; // Pointer to our main set\npublic:\n    CombinationIterator(string characters, int combinationLength) {\n        \n        int total = (1<<characters.size()); // Total subsets possible - 2^n\n        \n\t\t// Iterate through all the subsets\n        for(int mask{1}; mask<total; ++mask){\n            \n\t\t\t// If length/ size of subset is not equal to combinationLength, then skip it\n            if(__builtin_popcount(mask) != combinationLength)\n                continue;\n            \n\t\t\t//Now, we are sure that we have subset of desired length\n            set<char>my_set; // stores characters of subset lexicographically\n\t\t\t\n\t\t\t// Iterate through every available character\n            for(int i{}; i<characters.size(); ++i){\n                \n                int f = (1<<i);\n                \n\t\t\t\t// If character exists in our subset, add it to our set which we will use to generate our string\n                if(mask & f)\n                    my_set.insert(characters[i]);\n            }\n            \n           \n            string st{};\n\t\t\t\n\t\t\t// Here we generate the string in lexicographical order\n            for(auto c:my_set){\n                st.push_back(c);\n            }\n\t\t\t\n\t\t\t// And finally add it to our main set\n            combinations.insert(st);\n        }\n        \n\t\t// Initialize the pointer of our set to pointing to the begining of our set\n        cur = combinations.begin();\n        \n    }\n    \n\t// Here returns the string which is pointed by current pointer and moves forward\n    string next() {\n        return *cur++;\n    }\n    \n\t// Check whether current pointer is pointing towards  end or not\n    bool hasNext() {\n        return cur != combinations.end();\n    }\n};\n```\n**Time Complexity:** \n*For Constructor method:* ***O(2^(N) x 26)*** where *N* is the total numbers of characters. (Since we are generating all the subsets) and for each subset we are iterating all the unique characters which can be at max 26.\n*For Next Method:* **O(1)** because retrieving the value at iterator and incrementing an iterator takes constant time.\n*For hasNext:* **O(1)** because `cur != combinations.end()` is a contant time operation.\n\n**Space Complexity:** ***O(2^(N) x  K)*** where *2^(N)* are the total subsets and  *K* is the length of a subset.\n\nPlease do consider upvoting \uD83D\uDD3C if it helped you!
[]