<p>Given a string <code>s</code>, return <em>the </em><span data-keyword="lexicographically-smaller-string"><em>lexicographically smallest</em></span> <span data-keyword="subsequence-string"><em>subsequence</em></span><em> of</em> <code>s</code> <em>that contains all the distinct characters of</em> <code>s</code> <em>exactly once</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;bcabc&quot;
<strong>Output:</strong> &quot;abc&quot;
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;cbacdcbc&quot;
<strong>Output:</strong> &quot;acdb&quot;
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length &lt;= 1000</code></li>
	<li><code>s</code> consists of lowercase English letters.</li>
</ul>

<p>&nbsp;</p>
<strong>Note:</strong> This question is the same as 316: <a href="https://leetcode.com/problems/remove-duplicate-letters/" target="_blank">https://leetcode.com/problems/remove-duplicate-letters/</a>
/*

   method:
     1. X, sort: O(nlogn)
        then pick the different characters
        wrong: this is not to take all different and then sort it
               the index order in the res should be increasingly
               
     2. bitmask dp: O(n2^25), TLE
        since only 26 letters, an unsigned int can represent each combination by bits
        so check all previous found bits, and leave the best one
        the worst case to check for adding a character is 2^25 for all other 25 char
        combination
        
     3. X, greedy: O(n*26)
        think a previous best str as bs
        for each c in s
            if bs contains c
               new_s = bs remove c and then concate c into it
               if new_s < bs
                 bs = new_s
            else
               bs = bs + c
               
        wrong: think bcabc, it will get bac but best is abc
               
     4 greedy with alphabet: O(26^26*m + n) where m is the final size of res
       think a string includes c1,c2,...,ck and c1<c2<...<ck
       lets start from c1 to ck to see who can be in the res first
       said the start_i is the start index for ci, since it's the first one,
       just pick the leftmost index of ci (i.e. i < all other index of ci in [0..n-1])
          if [start_i...n-1] contains the other k - 1 chars
             ci is the first
             
          said the i is i1
             
       then as this idea, check if jth char in res
       the start index,i , of the jth c
       is to find start_i(j) < any other index of ci in [start_i(j-1)...n-1]
       (start_i(j-1) is from the previous round for the j-1th c)
       
       keep going till all chars is in res
       
       so one key point is
          1) how to get start_i quickly
            a) for each ci, iterate from the previous start_(i - 1) till n-1
               time O(n)
            b) use a stack for each char, bottom is rightmost and top is leftmost
               (i.e. from bottom to top is increasing)
               thus, if check the other char, its top is less than start_i, just pop it
               in fact, this can be handled after each ci is found
               as the ci found, based on its start_i, remove all the top of each stack
               so for start_(i + 1), no need to remove top
               time is O(1) for each finding and O(n) for whole removing 
          
          2) how to check if any other char except of char in res is in a [start..n-1]
            a) just loop from start->n-1 to check O(n)
            b) build a index table the all the ci, where last[ci] is the rightmost index
               => each time for start, check the latest index for the left char
                  (i.e. for the chars not put into res and range in [start..n-1])
                  time O(26)
                
          based on the (b) (both of (b)),
          for each char, we can prepare a vector, said arr_i
          the elements in arr_i is as stack in 1-b, arr_i[0] is bottom, arr_i.back() is top
          so arr_i[0] is the rightmost index for the char for the 2-b
       
       
*/
class Solution {
public:
    string smallestSubsequence(string s) {
        int n = s.length();
        
        unordered_map<char, vector<int>> index;
        for (int i = n - 1; i >= 0; --i)
            index[s[i]].push_back(i);
        
        int m = index.size();
        string res;
        while (res.length() < m) {
            char c = 'a';
            for (; c <= 'z'; ++c) {
                if (index.count(c) == 0)
                    continue;

                int count = count_if(index.begin(), index.end(),
                                    [&](auto &id) {
                                        return id.first != c
                                               && id.second[0] > index[c].back();
                                    });
                    
                if (count == index.size() - 1)
                    break;
            }
            
            res += c;
            
            // organize index for the next found
            //   remove the found char from index
            //   and remove the unused top index of stacks for the rest of chars
            int j = index[c].back();
            index.erase(c);
            for (auto &[tc, tv]: index)
                while (tv.back() < j)
                    tv.pop_back();
        }
        
        return res;
    }
};
9300