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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Remove Duplicate Letters

Difficulty: Medium

Problem Description

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.

Key Insights

  • Utilize a stack to build the result string in a way that ensures characters are in lexicographical order.
  • Use a frequency map to keep track of how many times each character appears.
  • Maintain a set to track characters that are currently in the stack to avoid duplicates.
  • As we iterate through the string, decide whether to add a character to the stack based on its lexicographical order and its remaining occurrences.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string s. Each character is processed at most twice (once added to the stack and once removed). Space Complexity: O(1), since the maximum size of the stack can be at most the number of distinct characters (constant, as there are only 26 lowercase letters).

Solution

We can use a greedy algorithm combined with a stack data structure to solve this problem. The stack will help us build the output string character by character. For each character in the string, we will decide whether to add it to the stack or to remove characters from the stack to maintain the lexicographical order. The frequency map helps us keep track of how many characters are left to process.

Code Solutions

def removeDuplicateLetters(s: str) -> str:
    stack = []
    in_stack = set()  # To track characters in the stack
    frequency = {char: 0 for char in s}

    # Count frequency of each character
    for char in s:
        frequency[char] += 1

    for char in s:
        # Decrease frequency since we are processing this character
        frequency[char] -= 1
        
        # If character is already in stack, skip it
        if char in in_stack:
            continue
        
        # Ensure the stack is in lexicographical order
        while stack and char < stack[-1] and frequency[stack[-1]] > 0:
            removed = stack.pop()
            in_stack.remove(removed)
        
        stack.append(char)
        in_stack.add(char)

    return ''.join(stack)
← Back to All Questions