C++ || Code with Explanation || Why use Stack?
Brief Overview:\nThe aim is to find the lexicographically shortest subsequence having distinct letters.\nThere would exist various permutations of subsequences 
**Brief Overview:**\nThe aim is to find the lexicographically shortest subsequence having distinct letters.\nThere would exist various permutations of subsequences that would have distinct letters. For instance if the String is "bcabc" , following are the subsequences possible:  { "bca" , "cab" , "bac" ,"abc" }, out of which lexicographically smallest is "abc" which is the answer.\n\n**How to Approach:**\n\n**Brute Force:**\nIn a Brute force Approach, we can use a Hashmap/Dictionary to map all the characters to all the indices and then generate all the possible subsequence permutations. Although this would give the correct answer, Computation would be very costly as generating and checking for every subsequence will take up factorial time complexity.\n\n**How to Optimize:**\nThe challenge is to think of a data structure or algorithm which can reduce the time complexity.\nFirst, we have to pick the characters if they are not already visited(to main distinctiveness). If that\'s the case, we\'ll try to pick these characters. We\'ll also make sure the previously picked character is smaller then the current character to maintain lexicographical order. To implement this we will use a **Stack!!**\nAs a general rule of thumb, a Stack data structure should be used to keep track of comparison among previously chosen/ next chosen elements.\n\n**How to Implement:**\nWe use the visited to keep track of selected characters.\nWe will loop through all characters of the string and take the following actions: \n* If the stack is empty, we\'ll put the current character into our stack.\n* We\'ll also keep here boolean array which will mark whether we have seen this character or not. So, if we are getting the same character again and we have already seen that. We\'ll ignore that character.\n* For every character, we will see if some greater characters are present in the stack, which can also be used later. As far as possible, we will make use of greater characters that are present farthest in the string. (How to do this is explained in the comments of the code).\n\n**Code (with comments) :**\n\n```\nclass Solution {\npublic:\n    string smallestSubsequence(string s) {\n        int n=s.size();\n        vector<bool> vis(26,0); // keeping track of visited letters\n        vector<int> lastInd(26,-1); // The last occurence of letter in the string\n        for(int i=0;i<n;i++){\n            lastInd[s[i]-\'a\']=i;\n        }\n        stack<char> st;     \n        for(int i=0;i<n;i++){\n            if(!vis[s[i]-\'a\']){\n                vis[s[i]-\'a\']=1;\n                // Checking only if letter not visited previously\n                // Once we meet this condition we are sure to push \n                // this character into the stack, before that \n                // we will check stack\'s surrent status and check for   \n                // any elements that can be removed. \n                while(!st.empty() && lastInd[st.top()-\'a\']>i && st.top()>s[i]){\n                    // If a greater letter is present again in the string \n                    //at  a a later index,lets use that index to use this character\n                    // , so for now we keep it out of stack and make it unvisited \n                    // to be able to be used later.\n                    vis[st.top()-\'a\']=0;\n                    st.pop();\n                }\n                st.push(s[i]);\n            }\n        }\n        string ans="";\n        // Pour out all the stack contents into a string and reverse it.\n        while(!st.empty()){\n            char c=st.top();\n            st.pop();\n            ans+=c;\n        }\n        reverse(ans.begin(),ans.end());\n        return ans;\n    }\n};\n```\n\n**Complexity Analysis :**\nTime: **O(N)** (one pass through the string every time, no nested loops)\nSpace: **O(N)** (lastInd array of size n, visited boolean array of size n, stack size)\n\nComment down below, If you have any queries or suggestions :)\nBest Wishes, \nAnurag
['Stack']