DSA problem

Remove Duplicate Letters

MediumStacksPattern: Stackstop150GoogleAmazonMicrosoftBloombergAdobe

Given a string s, remove duplicate letters so that every letter appears once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.

For example, given "bcabc", the only letters are a, b, c, and the lexicographically smallest ordering using each exactly once is "abc". Given "cbacdcbc", the answer is "acdb" — note that a comes first because it appears in the input and can be the leftmost, while b must come last because the only b remaining (after we choose to start with a) is at the end.

A brute force enumerating every distinct ordering and checking validity is exponential. The optimal approach is a monotonic stack with two helpful sidekicks: lastOccurrence[c], the last index at which character c appears in s, and inStack[c], whether c is currently on the stack.

We walk through s and for each character c: if c is already on the stack, skip it (we keep only its first useful occurrence). Otherwise, while the stack's top is greater than c AND that top character will appear again later in the string (i < lastOccurrence[top]), pop the top so a smaller letter can take its place — we'll re-add the popped letter later. Then push c and mark it as in-stack. At the end, reading the stack bottom-to-top gives the lexicographically smallest string with each letter exactly once. This runs in O(n) time and O(1) extra space (the alphabet is fixed at 26).

Examples

Example 1

Input: s = "bcabc"

Output: "abc"

Explanation: 'b' and 'c' are popped when we encounter 'a' because both 'b' and 'c' appear later. Then we push 'a', 'b', 'c' in order.

Example 2

Input: s = "cbacdcbc"

Output: "acdb"

Explanation: Push c, push b (b < c but c appears again later, pop c → push b), push a (a < b, b appears again later, pop b → push a), push c, push d, then skip c (already in stack), skip b? Actually careful: the answer "acdb" is the lex-smallest with each letter once.

Example 3

Input: s = "abacb"

Output: "abc"

Explanation: Distinct letters are a, b, c. The smallest arrangement preserving feasibility is "abc".

Constraints

1 <= s.length <= 10^4
s consists of lowercase English letters.

3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.

stackstringgreedymonotonic-stack

Browse all DSA problems