Remove Duplicate Letters
Medium · Stack · Explanation and code example
Monotone Stack with Remaining Counts
How it works
Build the smallest possible subsequence while keeping every distinct letter once. Before adding a letter, remove larger letters from the stack only if they occur again later. Remaining counts make each removal safe; a used set prevents duplicates.
Steps
- Count all remaining occurrences.
- For each letter, decrement its count and skip it if already used.
- Pop larger reusable letters, then push the current letter.
Complexity
- Time: O(n).
- Space: O(1) for the fixed 26-letter alphabet.
Things to watch for
- Never pop a letter whose remaining count is zero.
- Clear its used flag when popping.
- Keep relative order; sorting the letters is not a valid subsequence.
Python code example
import collections
class Solution:
def removeDuplicateLetters(self, s: str) -> str:
ans = []
count = collections.Counter(s)
used = [False] * 26
for c in s:
count[c] -= 1
if used[ord(c) - ord('a')]:
continue
while ans and ans[-1] > c and count[ans[-1]] > 0:
used[ord(ans[-1]) - ord('a')] = False
ans.pop()
ans.append(c)
used[ord(ans[-1]) - ord('a')] = True
return ''.join(ans)
C++ code example
class Solution {
public:
string removeDuplicateLetters(string s) {
string ans;
vector<int> count(128);
vector<bool> used(128);
for (const char c : s)
++count[c];
for (const char c : s) {
--count[c];
if (used[c])
continue;
while (!ans.empty() && ans.back() > c && count[ans.back()] > 0) {
used[ans.back()] = false;
ans.pop_back();
}
used[c] = true;
ans.push_back(c);
}
return ans;
}
};
Source and license
Explanation by LC Tracker. Code adapted from walkccc / Peng-Yu Chen · MIT license. Node types are supplied by LeetCode where needed.