Runtime Beats 3ms🔥 | 2 Solutions : Monotonic Stack | O(1) Space | 🔥Self Explanatory Comments🔥
\uD83D\uDE0A ~ \uD835\uDE52\uD835\uDE5E\uD835\uDE69\uD835\uDE5D \u2764\uFE0F \uD835\uDE57\uD835\uDE6E \uD835\uDE43\uD835\uDE5E\uD835\uDE67\uD835\uDE5A\uD835\uDE
\uD83D\uDE0A ~ \uD835\uDE52\uD835\uDE5E\uD835\uDE69\uD835\uDE5D \u2764\uFE0F \uD835\uDE57\uD835\uDE6E \uD835\uDE43\uD835\uDE5E\uD835\uDE67\uD835\uDE5A\uD835\uDE63\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n***Hey There It\'s Easy! Just Take A Look At The Code And Comments Within It. You\'ll Get It.\nStill Have Doubts! Feel Free To Comment, I\'ll Definitely Reply.***\n\n***Hey Everyone! If You Loved This Problem Than I Wanna Prefer An Another One Too Its Because It\'s The Exact Copy Of This Problem And It is :-\n"316 - Remove Duplicate Letters"\nThe Intuition & The Code Of "Leetcode 316" Is The Exact Same As This One, Hence I Want You To Try This "Leetcode 316" Yourself, First!***\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n***Both Accepted :\n-> Using 1 Stack\n-> Using Constant Auxiliary Space***\n\n# Complexity\n- *Time complexity: Mentioned in the code*\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- *Space complexity: Mentioned in the code*\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n**Approach 1 : Using 1 Stack**\n```\n// #1 Method to find the lexicographically smallest subsequence, using 1 stack - O(N) & O(N)\nstd::string smallestSubsequence(std::string s) {\n    int n = s.size();\n\n    std::string output = "";          // Stores the result string (output).\n    std::vector<bool> isTaken(26);    // Avoids the letter duplications.\n    std::vector<int> lastSeenIdx(26); // Maps the letters with their index at which they\'re seen at last.\n    std::stack<char> st;              // Maintains letters for building the smallest lexicographic subsequence.\n\n    // Map the letters with their index at which they\'re seen at last.\n    for(int i=0; i<n; i++) {\n        lastSeenIdx[s[i]-\'a\'] = i;\n    }\n\n    for(int i=0; i<n; i++) {\n        char currLetter = s[i];\n        // If its possible to take the current-letter (ith letter).\n        if(!isTaken[currLetter-\'a\']) {\n            // Pop all the letters smaller than the ith letter.\n            while(!st.empty() && lastSeenIdx[st.top()-\'a\'] > i && st.top() > currLetter) {\n                isTaken[st.top()-\'a\'] = false;\n                st.pop();\n            }\n            // Push the ith letter to the stack.\n            st.push(currLetter);\n            // Mark the ith letter untakable for the next time, as we are aiming for the distinct letters.\n            isTaken[currLetter-\'a\'] = true;\n        }  \n    }\n\n    // Pop and store each letter to the result string (output).\n    while(!st.empty()) {\n        output.push_back(st.top());\n        st.pop();\n    }\n\n    // Reverse the result string to get the lexicographically smallest subsequence.\n    std::reverse(begin(output), end(output));\n    \n    // Return the result string (output).\n    return output;\n}\n```\n**Approach 2 : Using Constant Auxiliary Space**\n```\n// #2 Method to find the lexicographically smallest subsequence, using constant auxiliary space - O(N) & O(1)\nstd::string smallestSubsequence(std::string s) {\n    int n = s.size();\n\n    std::vector<bool> isTaken(26);    // Avoids the letter duplications.\n    std::vector<int> lastSeenIdx(26); // Maps the letters with their index at which they\'re seen at last.\n    std::string output = "";          // Stores the result string (output).\n\n    // Map the letters with their index at which they\'re seen at last.\n    for(int i=0; i<n; i++) {\n        lastSeenIdx[s[i]-\'a\'] = i;\n    }\n\n    for(int i=0; i<n; i++) {\n        char currLetter = s[i];\n        // If its possible to take the current-letter (ith letter).\n        if(!isTaken[currLetter-\'a\']) {\n            // Pop all the letters smaller than the ith letter.\n            while(!output.empty() && lastSeenIdx[output.back()-\'a\'] > i && output.back() > currLetter) {\n                isTaken[output.back()-\'a\'] = false;\n                output.pop_back();\n            }\n            // Push the ith letter to the "output".\n            output.push_back(currLetter);\n            // Mark the ith letter untakable for the next time, as we are aiming for the distinct letters.\n            isTaken[currLetter-\'a\'] = true;\n        }  \n    }\n\n    // Return the result string (output).\n    return output;\n}\n```\n\uD835\uDDE8\uD835\uDDE3\uD835\uDDE9\uD835\uDDE2\uD835\uDDE7\uD835\uDDD8 \uD835\uDDDC\uD835\uDDD9 \uD835\uDDEC\uD835\uDDE2\uD835\uDDE8 \uD835\uDDDF\uD835\uDDDC\uD835\uDDDE\uD835\uDDD8 \uD835\uDDE7\uD835\uDDDB\uD835\uDDD8 \uD835\uDDE6\uD835\uDDE2\uD835\uDDDF\uD835\uDDE8\uD835\uDDE7\uD835\uDDDC\uD835\uDDE2\uD835\uDDE1 \uD83D\uDC4D
['String', 'Stack', 'Greedy', 'Monotonic Stack', 'C++']