<p>Given a string <code>s</code>, remove duplicate letters so that every letter appears once and only once. You must make sure your result is <span data-keyword="lexicographically-smaller-string"><strong>the smallest in lexicographical order</strong></span> among all possible results.</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;= 10<sup>4</sup></code></li>
	<li><code>s</code> consists of lowercase English letters.</li>
</ul>

<p>&nbsp;</p>
<p><strong>Note:</strong> This question is the same as 1081: <a href="https://leetcode.com/problems/smallest-subsequence-of-distinct-characters/" target="_blank">https://leetcode.com/problems/smallest-subsequence-of-distinct-characters/</a></p>

class Solution {
public:

    string removeDuplicateLetters(string s) {  
        string result;

        unordered_map<char, int> lastPos;
        for (int i = 0; i < s.size(); ++i)
            lastPos[s[i]] = i;

        for (int i = 0; i < s.size(); ++i)
        {
            cout << result << endl;
            if (result.empty())
            {
                result.push_back(s[i]);
                continue;
            }

            char current = s[i];            
            if (find(result.begin(), result.end(), current) != result.end())
                continue;

            char prev = result.back();
            result.push_back(current);

            while (result.size() > 1 && current < prev && lastPos[prev] > i)
            {
                result.pop_back();
                if (result.size() > 1)
                    prev = result[result.size() - 2];
                result.back() = current;
            }
        }
        return result;
    }



    unordered_set<char> chars;
    priority_queue<string, vector<string>, std::greater<string>> candidates;

    string removeDuplicateLetters2(string s) {  

        if (s.size() <= 1)
            return s;

        for (char c : s)
            chars.emplace(c);

        generate(0, chars.size(), {}, s);

        if (candidates.empty())
            abort();
        return candidates.top();
    }

    void generate(int offset, int k, string path, const string& s)
    {
        if (k == 0)
        {
            string candidate;            
            cout << path << endl;
            
            bool good = true;
            int lastSeen = -1;
            for (char c : path)
            {
                int i = atoi(string{c}.c_str());                
                candidate.push_back(s[i]);                
            
                if (lastSeen != -1 && i <= lastSeen)
                {
                    good = false;
                    break;
                }
                lastSeen = i;
            }

            bool seen[256];
            for (int i = 0 ; i != candidate.length(); i++) {
                int index = candidate[i];
                if (seen[index])
                {
                    good = false;
                    break;
                };
                seen[index] = true;
            }
                
            if (good)
            {
                candidates.push(candidate);            
                cout << candidate << endl;
            }

            return;
        }

        for (int i = offset; i <= s.size() - k; ++i)
        {
            path += to_string(i);
            generate(offset + 1, k - 1, path, s);
            path.pop_back();
        }
    }
};
9400