We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Remove Duplicate Letters

Number: 316

Difficulty: Medium

Paid? No

Companies: Expedia, Bloomberg, Google, Microsoft, Meta, Increff, Oracle, Amazon, Yahoo, TikTok, Apple, Adobe, BNY Mellon, DRW, ByteDance, FactSet

Problem Description

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

Key Insights

  • Use a monotonic stack to build the resulting string.
  • Store the last occurrence of each character to know if it can be safely removed.
  • Use a set (or boolean array) to track which characters have been added to avoid duplication.
  • Greedily remove characters from the stack if the current character is smaller and the top of the stack appears again later in the string.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string, because each character is processed once. Space Complexity: O(n) for the stack and auxiliary data structures.

Solution

We iterate over the string while maintaining a stack and a record of whether each character is already in the result. For each character, if it is already in the result, we skip it. Otherwise, we check if the current character is smaller than the last character in the stack and if that last character appears later in the string. If both conditions are met, we pop it from the stack so that the overall result remains lexicographically minimal. Then we add the current character to the stack and mark it as seen.

Code Solutions

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        # Map each character to its last occurrence index
        last_occurrence = {c: i for i, c in enumerate(s)}
        stack = []  # Monotonic stack to build the result
        seen = set()  # Set to record characters already in the stack
        
        # Iterate over each character and its index
        for i, char in enumerate(s):
            # Skip if character is already in the stack
            if char in seen:
                continue
            # Remove characters that are larger than current character and appear later
            while stack and char < stack[-1] and last_occurrence[stack[-1]] > i:
                removed_char = stack.pop()
                seen.remove(removed_char)
            stack.append(char)
            seen.add(char)
        # Join the stack to form the final result
        return "".join(stack)
← Back to All Questions