[C++] Stack-based Solution Explained, 100% Time, ~50% Space
Now we have a tricky one to rein in, since we might be tempted to go for some approaches that would collapse once you factor in some specific scenarios.\n\nMy s
Now we have a tricky one to rein in, since we might be tempted to go for some approaches that would collapse once you factor in some specific scenarios.\n\nMy solution might not be the perfect one, but I found it to be rather understandable and, not secondarily, performing enough, so allow me to go into more detail about it.\n\nWe start with our usual support variables:\n* `res` will store our result, as usual;\n* `st` (I know, again: I really suck at naming) is a stack of character we will use to figure out what to keep and what to discard (more about it later);\n* `seen` is an array of `26` booleans, we will initialise to `false`;\n* `last`, similarly to the previous, is an array of `26` integers that will store the value of the last indexes of each character in the input -  you don\'t really need initialising it if you use more complex logic, but setting all its values to `0` was easier and cheaper to manage;\n* `len` will store the input string size;\n\nFirst of all we are going to start populating `last` with proper values, starting from the end of the string and moving on either up to the first character or until we have met all possible `26` different ones - which probably is going to be a massive computational save on massive random strings.\n\nNote that here as when using `seen`, we will normalise all characterss to be in the `0 - 25` range subtracting `\'a\'` from their actual value.\n\nNow comes the core of our function: building and updating a stack with all the encountered characters in order; to do so, we will run through the whole string (this time from the beginning) and:\n* normalising each character `c`, as explained right above;\n* checking if `seen[c]`, in which case we just placidly `continue`;\n* otherwise, while we have something in the stack, we pop as long as `c` is lexicographically less than the current `st.top()` and if `i` is before the previously computed last index of the top of the stack (`last[st.top()]`);\n* each pop will also make so that we turn the matching cell in `seen` back to `false` (since we need to keep track about how we removed that character from our stack);\n* in any case, we add `c` on top of the stack `st`;\n* finally, we set `seen[c] = true`.\n\nOnce we are done looping through the would string, we can just pop all the content of the stack into our accumulator `res`, just remembering that this process will give us our result string in reverse, so we just have to `reverse` it again and finally can return it :)\n\nThe code:\n\n```cpp\nclass Solution {\npublic:\n    string smallestSubsequence(string s) {\n        // support variables\n        string res = "";\n        stack<char> st;\n        bool seen[26];\n        for (bool &s: seen) s = false;\n        int last[26], len = s.size();\n        for (int &l: last) l = 0;\n        for (int i = len - 1, charCount = 0; charCount < 26 && i >= 0; i--) {\n            // adding the last index when not yet found\n            if (!last[s[i] - \'a\']) {\n                charCount++;\n                last[s[i] - \'a\'] = i;            }\n        }\n        // building a stack with all the characters in a valid sequence\n        for (int i = 0, c; i < len; i++) {\n            c = s[i] - \'a\';\n            if (seen[c]) continue;\n            while (!st.empty() && c < st.top() && i < last[st.top()]) {\n                seen[st.top()] = false;\n                st.pop();\n            }\n            st.push(c);\n            seen[c] = true;\n        }\n        // recomposing the string from the stack\n        while (!st.empty()) {\n            res.push_back(st.top() + \'a\');\n            st.pop();\n        }\n        reverse(begin(res), end(res));\n        return res;\n    }\n};\n```
['String', 'Stack', 'C', 'C++']