<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:
    def removeDuplicateLetters(self, s: str) -> str:
        '''
        Interview Guide: "Remove Duplicate Letters" Problem
        '''
        seen = set()
        ord_stk = []
        last_occurrence = {c: i for i,c in enumerate(s)}

        for i,c in enumerate(s):
            if c not in seen:
                if len(ord_stk)>0:
                    while ord_stk and c<ord_stk[-1] and i<last_occurrence[ord_stk[-1]]:
                        top_c_stk = ord_stk.pop()
                        seen.discard(top_c_stk)
                    ord_stk.append(c)
                else:
                    ord_stk.append(c)

                seen.add(c)

        return "".join(ord_stk)
16600