<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 str) {
      stack<char> s;
      string result;

      unordered_map<char, int> indices;
      unordered_set<char> taken;
      for (int i = str.size() - 1; i >= 0; --i) {
        if (!indices.count(str[i])) {
          indices[str[i]] = i;
        }
      }

      for (int i = 0; i < str.size(); ++i) {
        char ch = str[i];
        if (!taken.count(ch)) {
          while (!s.empty() && s.top() >= ch && indices[s.top()] > i) {
            taken.erase(s.top());
            s.pop();
          }
          s.push(ch);
          taken.insert(ch);
        }
      }

      if (!s.empty()) {
        string temp;
        while (!s.empty()) {
          temp.push_back(s.top());
          s.pop();
        }
        result.insert(result.end(), temp.rbegin(), temp.rend());
      }

      return result;
    }
};
9500