Beginner Friendly Simple C++ Code
IntuitionTo find the lexicographically smallest subsequence of a string that contains all the distinct characters exactly once, we need to ensure two things:We
# Intuition\nTo find the lexicographically smallest subsequence of a string that contains all the distinct characters exactly once, we need to ensure two things:\n\nWe must include every distinct character in the resulting subsequence.\nThe sequence must be in lexicographical order. To achieve this, we need to track the remaining occurrences of each character and maintain the order by using a stack data structure to help with the sequence formation.\n\n# Approach\nFrequency Count: Count the frequency of each character in the input string s.\nStack for Result: Use a stack to build the resulting subsequence.\nInclusion Tracking: Use an array to track if a character is already included in the current result.\nIterate through the String: For each character, do the following:\nDecrease its count in the frequency array.\nIf the character is already in the stack, skip it.\nIf the character is not in the stack, ensure the stack remains lexicographically smallest by popping elements from the stack that are greater than the current character and can appear later in the string.\nPush the current character onto the stack and mark it as included.\nConstruct the Result: Convert the stack to a string to get the final result.\n# Complexity\n- Time complexity:\nO(n), where n is the length of the string. We process each character in the string once.\n\n- Space complexity:\nO(1), since the size of the frequency and inclusion arrays are fixed at 26 (for the 26 lowercase English letters), and the stack will hold at most 26 characters.\n# Code\n```cpp []\nclass Solution {\npublic:\n    string smallestSubsequence(string s) {\n    // Frequency count of each character\n    int freq[26] = {0};\n    for (char c : s) {\n        freq[c - \'a\']++;\n    }\n\n    // Stack to store the result characters\n    stack<char> st;\n    // Boolean array to check if a character is in the current result\n    bool inStack[26] = {false};\n    \n    for (char c : s) {\n        // Decrement the frequency of the current character\n        freq[c - \'a\']--;\n\n        // If character is already in stack, skip it\n        if (inStack[c - \'a\']) {\n            continue;\n        }\n\n        // Ensure the stack remains lexicographically smallest\n        while (!st.empty() && st.top() > c && freq[st.top() - \'a\'] > 0) {\n            inStack[st.top() - \'a\'] = false;\n            st.pop();\n        }\n\n        // Push current character onto the stack\n        st.push(c);\n        inStack[c - \'a\'] = true;\n    }\n\n    // Convert the stack to a string and return\n    string result;\n    while (!st.empty()) {\n        result = st.top() + result;\n        st.pop();\n    }\n\n    return result;\n    }\n\n\n};\n```
['C++']