Domain 2MediumCORE

Remove Duplicate Letters

We are given a string s consisting of lowercase English letters. The goal is to construct a subsequence that contains every unique character present in the original string exactly once. Among all possible subsequences satisfying this condition, we must return the one that is lexicographically smallest (i.e., 'abc' comes before 'acb').

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#String#Stack#Greedy

316. Remove Duplicate Letters

Model: qwen3.5:9b
Topics: String,Stack,Greedy
FAANG asked: 1
Acceptance rate: 39.3%


Problem Breakdown

We are given a string s consisting of lowercase English letters. The goal is to construct a subsequence that contains every unique character present in the original string exactly once. Among all possible subsequences satisfying this condition, we must return the one that is lexicographically smallest (i.e., “abc” comes before “acb”).

Inputs: A single string s with length between 1 and 10410^4. Outputs: A string containing each unique character from s exactly once. Constraints/Edge Cases:

  • The input contains only lowercase English letters (‘a’-‘z’).
  • Every distinct character in the input must appear at least once in the output; we cannot drop a character entirely just because it appears multiple times, nor can we include duplicates.
  • Since s is non-empty (constraint ≥1\ge 1), an empty result isn’t possible unless the string itself was somehow invalid, but per constraints, valid input always yields at least one unique char in output.

Intuition

A brute-force approach would be to generate all subsequences that contain every distinct character exactly once and then sort them lexicographically. However, for a string of length NN, there are potentially many such subsequences (roughly proportional to combinations), making this exponential or at least very slow (O(N!)O(N!) in worst case permutations). We need an efficient greedy strategy.

The core insight is that we want the smallest possible character as early as possible in our result string. However, if a smaller character appears later in s, and removing its current occurrence prevents us from including it (because there are no more instances), we must keep the earlier one. Conversely, if we have already placed a larger character on our “result stack” but encounter a smaller character that is available again later, we should discard the larger character to place the smaller one first—provided we don’t lose the ability to include the discarded character entirely (i.e., there are more instances of it coming up).

This suggests using a monotonic increasing stack. We iterate through s, and for each character:

  1. If it’s already in our result, skip it (we have one valid instance).
  2. If we encounter a smaller character than the top of our stack, check if the top-of-stack character appears again later in s.
  3. If yes, pop the larger character from the stack and remove it from our “seen” set so we can pick up its next occurrence when needed.
  4. Push current character onto stack and mark as seen.

Approach

  1. Preprocessing: First, calculate the last index of every unique character in s. This allows us to know if a popped character will appear again later (i.e., we can safely discard it). We store this in an array or hash map (last_occurrence).
  2. Data Structures:
    • A list acting as a stack (stack) to build the result string.
    • A boolean set (seen) to track characters currently present on the stack (to ensure uniqueness within our current construction).
  3. Iteration: Loop through each character c in s:
    • If c is already in seen, skip it; we have a valid instance of this char already placed or pending.
    • While the stack is not empty, and the top element (stack[-1]) is lexicographically larger than c, AND there are more occurrences of that top element later (checked via last_occurrence):
      • Pop from stack.
      • Remove popped character from seen.
    • Push c onto the stack and add to seen.
  4. Result: Join the characters in the stack at the end.

Complexity Analysis

  • Time Complexity: O(N)O(N), where NN is the length of string s. We iterate through s once (O(N)O(N)). Each character is pushed onto the stack exactly once and popped at most once. Operations inside the loop are constant time (array lookups/set operations for 26 chars).
  • Space Complexity: O(1)O(1) auxiliary space relative to input size, specifically proportional to the alphabet size Σ\Sigma (≤26\le 26) because we only store unique characters in stack and seen. The last occurrence map is also constant size (size of alphabet).

Solution

def removeDuplicateLetters(s: str) -> str:
    # Map each character to its last index for O(1) lookup later.
    # Using a dictionary or list; here using dict for clarity on indices.
    last_occurrence = {char: i for i, char in enumerate(s)}
    
    stack = []
    seen = set()

    for i, c in enumerate(s):
        # If character is already included in our result (stack), skip it 
        # because we want to keep the one currently on stack unless popped.
        if c in seen:
            continue
        
        # While stack not empty and current char 'c' is smaller than top of stack,
        # AND there are more occurrences of the top element later in string (safe to pop).
        while stack and last_occurrence[stack[-1]] > i and stack[-1] > c:
            popped = stack.pop()
            seen.remove(popped)
        
        # Push current char onto stack and mark as seen.
        stack.append(c)
        seen.add(c)

    return "".join(stack)

Edge Cases Handled

  • All unique characters: The loop pushes every character in order of appearance since no duplicates exist to trigger the pop logic, resulting in a sorted subsequence if input was already sorted.
  • Reverse sorted string (e.g., “cba”): ‘c’ pushed. When ‘b’ comes, last_occurrence['c'] is checked; if another ‘c’ exists later, ‘c’ pops to allow smaller ‘b’. If no more ‘c’, it stays on stack despite being larger than ‘b’.
  • String with only one instance of a character: The condition last_occurrence[stack[-1]] > i ensures we never pop the last occurrence, guaranteeing every unique char is preserved in output.