316. Remove Duplicate Letters

Time: O(n)

Space: O(1)

Intuition

Greedy + monotonic stack: for each character, pop characters from the stack that are greater than the current one AND still appear later in the string (so they can be included later). This ensures the lexicographically smallest result while including each character exactly once.

Algorithm

1Count remaining occurrences of each character. Track which characters are in the stack (inStack set).
2For each character c: decrement count[c]. If c is in stack, skip.
3While stack top > c AND count[stack.top] > 0: pop top, remove from inStack.
4Push c, add to inStack.
5Return stack as string.

Example Walkthrough

Input: "cbacdcbc"

1.c(count: c=4,b=2,a=1,d=1). Process c: stack=[c].
2.b: c>b and count[c]=3>0 -> pop c. stack=[b].
3.a: b>a and count[b]=1>0 -> pop b. stack=[a].
4.c: push. stack=[a,c]. d: push. stack=[a,c,d]. c: in stack skip. b: push. stack=[a,c,d,b]. c: in stack, skip.

Output: "acdb"

Common Pitfalls

•Only pop a character if it still appears later (count > 0) - otherwise removing it would lose the character entirely.

316.cs

// Approach: Greedy monotonic stack to build the lexicographically smallest result.
// Pre-count character frequencies; use a boolean array to track characters already in the stack.
// For each character: if already in stack, skip it.
// Otherwise, pop the stack top while: top > current AND top appears again later (count > 0).
// Push the current character and mark it as 'in stack'.
// Decrement count for each character processed regardless of whether it is pushed.
// Time: O(n) Space: O(1) since the character set is fixed at 26 letters.

public class Solution
{
    public string RemoveDuplicateLetters(string s)
    {
        StringBuilder sb = new StringBuilder();
        int[] count = new int[128];
        bool[] used = new bool[128];

        foreach (char c in s)
            ++count[c];

        foreach (char c in s)
        {
            --count[c];
            if (used[c])
                continue;
            while (sb.Length > 0 && Last(sb) > c && count[Last(sb)] > 0)
            {
                used[Last(sb)] = false;
                sb.Length--;
            }
            used[c] = true;
            sb.Append(c);
        }

        return sb.ToString();
    }

    private char Last(StringBuilder sb)
    {
        return sb[sb.Length - 1];
    }
}

Was this solution helpful?