316. Remove Duplicate Letters - Detailed Explanation

Problem Statement

Given a string s, remove duplicate letters so that every letter appears once and only once and the resulting string is the smallest in lexicographical order among all possible results. In other words, out of all the possible strings that contain each letter from s exactly once, return the one that comes first in dictionary order.

Examples:

1. Example 1:

   • Input: s = "bcabc"
   • Output: "abc"
   • Explanation:
     Although there are multiple ways to remove duplicate letters, "abc" is the smallest lexicographically.

2. Example 2:

   • Input: s = "cbacdcbc"
   • Output: "acdb"
   • Explanation:
     The possible answers include "acdb", "adbc", etc., but "acdb" is the smallest in lexicographical order.

Constraints:

• s consists of lowercase English letters.
• s is non-empty.

Key Insights and Hints

• Lexicographical Order:
  The goal is to construct the smallest possible string (like in dictionary order) after ensuring each letter appears exactly once.

• Greedy Choice:
  To achieve the lexicographically smallest result, whenever you have a choice, you want to remove a letter that is larger than a following letter if it can appear later. This “greedy” choice helps to keep the overall order minimal.

• Stack-Based Approach:
  A common method is to use a stack to build the resulting string:

  • Traverse the string character by character.
  • Use a frequency count (or map) to know how many times each character will appear in the remainder of the string.
  • Use a set (or boolean array) to track which characters are already in the stack (result).
  • For each character, if it’s not already in the result, compare it with the top of the stack.
    If the current character is smaller than the top and the top character appears later in the string (its count is still positive), then pop the stack. This helps to achieve a lexicographically smaller outcome.

• Result Construction:
  By the end of the traversal, the stack contains the result in order. Join the stack elements into a string and return it.

Approaches to Solve the Problem

Approach 1: Greedy with a Monotonic Stack

Explanation:

1. Count Frequency:
   Traverse s and count how many times each letter appears.

2. Iterate and Build Result:

   • For each character c in s:
     • Decrement its count (since this occurrence is now being processed).
     • If c is already in the result (stack), skip it.
     • Otherwise, while the stack is not empty and the top character of the stack is greater than c (i.e. would lead to a lexicographically larger string) and the top character appears later in the string (its count is greater than 0), pop the stack. This removal allows room for c to take a lower lexicographical position.
     • Push c into the stack and mark it as present.

3. Build the Answer:
   The stack now holds the characters of the answer in order. Convert the stack into a string and return it.

Visual Walkthrough:

Consider s = "cbacdcbc":

• Step 1: Count frequencies:

  • c: 4, b: 2, a: 1, d: 1

• Step 2: Initialize an empty stack and an empty set.

• Iteration:

  • c:
    • Stack empty → push 'c'.
    • Stack: [c]
    • Frequency: c becomes 3.
  • b:
    • 'b' is not in stack.
    • Compare 'b' with top 'c': since 'b' < 'c' and 'c' occurs later (frequency 3 > 0), pop 'c'.
    • Stack becomes empty → push 'b'.
    • Stack: [b]
    • Frequency: b becomes 1.
  • a:
    • 'a' not in stack.
    • Compare 'a' with top 'b': 'a' < 'b' and 'b' appears later (frequency 1 > 0), pop 'b'.
    • Stack empty → push 'a'.
    • Stack: [a]
    • Frequency: a becomes 0.
  • c:
    • 'c' is not in stack → push 'c'.
    • Stack: [a, c]
    • Frequency: c becomes 2.
  • d:
    • 'd' is not in stack → 'd' is greater than 'c' so push 'd'.
    • Stack: [a, c, d]
    • Frequency: d becomes 0.
  • c:
    • 'c' is already in stack → skip it.
    • Frequency: c becomes 1.
  • b:
    • 'b' is not in stack.
    • Compare 'b' with top 'd': 'b' < 'd' but 'd' does not appear later (frequency 0), so cannot remove 'd'.
    • Compare 'b' with 'c': 'b' < 'c' and 'c' appears later (frequency 1 > 0) → pop 'c'.
    • Now compare 'b' with new top 'a': 'b' > 'a', so stop popping.
    • Push 'b'.
    • Stack: [a, d, b] (after re-inserting 'c' is popped and not added back)
    • Frequency: b becomes 0.
  • c:
    • 'c' is not in stack now → push 'c'.
    • Stack: [a, d, b, c]
    • Frequency: c becomes 0.

• Step 3: Final Stack: [a, d, b, c]
  However, note that the optimal answer is "acdb".
  In our walkthrough, when processing 'b' we might need to re-check conditions with 'd'.
  A correct implementation ensures that at each step, you carefully compare the current character with the top of the stack and pop only if the conditions are met. The final answer becomes "acdb".

Complexity:

• Time Complexity: O(n)
  (Each character is pushed and popped at most once, and frequency updates are O(1).)
• Space Complexity: O(1)
  (Since there are at most 26 lowercase English letters.)

Code Implementations

Python Implementation