[C++] | Permuting Pointers! | Pictures + Detailed Explanation + Commented Code | #NovemberChallenge
This problem might seem like an implementation nightmare considering all the casework, but it is actually quite inuitive once you get the hang of how the pointe
This problem might seem like an implementation nightmare considering all the casework, but it is actually quite inuitive once you get the hang of how the pointers move! \n\n**Idea**\nImagine *combinationLength = 1*. If that is the case then we would simply go over all the characters of the initial string! \n![image](https://assets.leetcode.com/users/images/340f380e-4a60-4768-a802-5b849c1e7fd1_1636849714.2805321.png)\nThe cell in red shows what is to be returned with each *next* call. Hence maintaining a *pointer* and incrementing such that it points to the next character after every *next* call would work. \n\nWe build our case for *combinationLength > 1* using this example. When we need to return multiple characters, it only makes sense to use multiple pointers! Like we used one pointer (i) in the previous example, we will need to maintain and handle multiple pointers (i, j, k..);  as many pointers as *combinationLength*. But as you can imagine, handling *combinationLength* can get very tedious very fast! How else can we maintain that many pointers?\n\n**An array of ponters!**\nThat\'s right! Since the size of the string is small (n <= 15), we can create a boolean array *bits* of size *n* where *bits[i] == 1* would represent that the ith character has a pointer, and *bits[i] == 0* would represent the opposite! Here are some key points regarding the *bits* array:\n* At all times, there are exactly *combinationLength* number of 1s in the array. This indicates that there are exactly *combinationLength* number of pointers.\n* The first permutation of *bits* would have the first *combinationLength* elements set to 1, indicating the lexicographically smallest combination.\n* The last permutaiton of *bits* would have the last *combinationLength* elements set to 1, indicating the lexicographically largest combination.\n* We need to permute the *bits* array in such a way that it yeilds the lexicographically greater combination each time.\n\nConsider a testcase: *characters = "abcd", combinationLength = 2*\n![image](https://assets.leetcode.com/users/images/81e521b6-1d09-477a-af47-b899701e5ff5_1636850803.981569.png)\nEvery row represents a *next* call. Clearly after the last row, there can be no *next* call.\n\nNow that the use of *bits* is clear, we just need to see how to permute it with each call!\n**The last 1 moves along!***\nThat\'s right! For most of the *next* calls, we will only need to shift the last 1 ahead by one step. Look at the first three rows of the previous image and notice that the last 1 shifts ahead by one in each call (the red cell moves ahead), till it reaches the end. Perfect! But what happens when it reaches the end? There are no further shifts possible for it. Hence, some other element must move. But which one? Since we want the lexicographically greater element, we will have to shift a 1 ahead such that it occupies the place of a 0. There can be multiple such 1s, so which one do we move? The rightmost such 1, since we want exactly the next lexicographical permutation. \n\nOof that was too much to take in, wasn\'t it? Let me use an example to further explain it.\n![image](https://assets.leetcode.com/users/images/45e94ec8-c378-4ec2-b865-47702ad18610_1636851799.2509944.png)\nTo summarise, when the last 1 reaches the end, then we need to do the following:\n* Find the rightmost free 1, i.e, which has 0 right after it.\n* Shift it one step ahead.\n* Take all the 1s at the end and shift them after the newly shifted 1!\n\nFurther we maintain a boolean *possible* which tracks if the next permutation is possible or not. Interstingly, it only turns false when the last permutation is reached!\n\nThat\'s it!\n\n\n**Implementation**\nOne can implement it in many ways but the core idea remains the same. I have added comments for better understanding.\n\n**C++**\n```\nclass CombinationIterator {\npublic:\n\n\t// Array of pointers\n    vector<bool> bits; \n    int n;\n\t\n\t// Boolean tracking if the next permutation is possible\n    bool possible = true;\n    string str;\n\t\n\t// Length of the combination required\n    int len;\n    \n    CombinationIterator(string s, int len) {\n        str = s;\n        this -> len = len;\n        n = s.size();\n        bits.resize(n, 0);\n        \n        // First Permutation\n        for(int i = 0; i < len; i++) {\n            bits[i] = 1;\n        }\n    }\n    \n    string next() {\n        string ans = "";\n        \n        // Generating the current combination\n        for(int i = 0; i < n; i++) {\n            if(bits[i])\n                ans += str[i];\n        }\n        \n        // Permuting bits so that it points to the next combination\n        \n        // Case 1: Last bit is not set!\n        if(bits[n - 1] == 0) {\n            // Simply shift the rightmost free 1 ahead!\n            for(int i = n - 1; i >= 0; i--) {\n                if(bits[i]) {\n                    bits[i + 1] = 1;\n                    bits[i] = 0;\n                    break;\n                }\n            }\n        } else {\n            \n            // Count the number of 1s at the end and simultaneously \n            // setting them to 0\n            int onesAtLast = 0;\n            int i = n - 1;\n            while(i >= 0 && bits[i]) {\n                bits[i] = 0;\n                onesAtLast++;\n                i--;\n            }\n            \n            // If all 1s are at the end, then we have already covered\n            // the final combination, and no other combination\n            // is possible!\n            if(onesAtLast == len) {\n                possible = false;\n            } else {\n                \n                // Now finding the rightmost free 1\n                while(i >= 0 && bits[i] == 0) {\n                    i--;\n                }\n                \n                // Shifting it ahead\n                bits[i++] = 0;\n                bits[i++] = 1;\n                \n                // Shifting onesAtLast number of 1s after the \n                // newly shifted 1\n                while(onesAtLast--) {\n                    bits[i++] = 1;\n                }\n            }\n        }\n        \n        // Returning the computed string\n        return ans;\n    }\n    \n    bool hasNext() {\n        return possible;\n    }\n};\n```\n\n**Complexity Analysis**\n*Space Complexity (Auxiliary): O(n)*\n*Time Complexity: O(1) for hasNext, O(n) for next*\n
['Simulation']