LeetCode 316: Remove Duplicate Letters Solution in Python – A Step-by-Step Guide

What Is LeetCode 316: Remove Duplicate Letters?

In LeetCode 316: Remove Duplicate Letters, you’re given a string s, and your task is to remove duplicate letters to create a new string where each letter appears exactly once, in the smallest lexicographical order possible while preserving the relative positions of letters. For example, "bcabc" becomes "abc"—removing extra b and c to get the smallest unique sequence. This problem tests your ability to balance greediness with order, sharing ties with LeetCode 402: Remove K Digits.

Problem Statement

• Input: A string s of lowercase English letters.
• Output: A string—smallest lexicographical order with no duplicates, using all unique letters from s.
• Rules:
• Each letter appears once.
• Relative order of letters in original string is maintained.
• Result must be lexicographically smallest.

Constraints

• 1 <= s.length <= 10⁴
• s contains only lowercase English letters.

Examples

• Input: "bcabc"
• Output: "abc"
• Input: "cbacdcbc"
• Output: "acdb"
• Input: "leetcode"
• Output: "letcod"

Understanding the Problem: Crafting the Smallest Unique String

To solve LeetCode 316: Remove Duplicate Letters in Python, we need to remove duplicates from s while ensuring every unique letter appears once, in the smallest possible order, respecting their original sequence. A naive approach—generating all unique subsequences and picking the smallest—is O(2^n), far too slow. Instead, we’ll use:

• Best Solution (Stack-Based Greedy): O(n) time, O(1) space—fast and smart.
• Alternative Solution (Recursive): O(n) time with multiple passes, O(n) space—clear but less efficient.

Let’s start with the stack-based solution, explained in a beginner-friendly way.

Best Solution: Stack-Based Greedy Approach

Why This Is the Best Solution

The stack-based greedy approach is the top choice for LeetCode 316 because it’s efficient—O(n) time, O(1) space (ignoring output)—and elegantly builds the result in one pass. It uses a stack to maintain the smallest lexicographical order, popping larger letters when smaller ones appear later, guided by letter counts. It’s like crafting a word puzzle live—intuitive and quick once you get it!

How It Works

Think of this as building the string step-by-step:

• Step 1: Track Last Occurrences:
• Record the last index of each letter in s.
• Step 2: Build with a Stack:
• For each letter:
• Skip if already in stack.
• Pop larger letters from stack if they appear later.
• Push current letter.
• Step 3: Why It Works:
• Greedy choice ensures smallest order.
• Last occurrence check preserves all letters.

It’s like stacking letters, keeping only the best!

Step-by-Step Example

Example: s = "cbacdcbc"

• Last Occurrences: c:7, b:6, a:3, d:4
• Stack Process:
• c: Stack = [c]
• b: b<c, (c="" 7),="" at="" c="" later="" pop="" stack="[b]</li">
• a: a<b, (b="" 6),="" at="" b="" later="" pop="" stack="[a]</li">
• c: Stack = [a,c]
• d: Stack = [a,c,d]
• c: Skip (in stack)
• b: Stack = [a,c,d,b]
• c: Skip
• Result: "acdb"

Code with Detailed Line-by-Line Explanation

Copy codeclass Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        # Track last occurrence of each letter
        last_occurrence = {}
        for i, char in enumerate(s):
            last_occurrence[char] = i

        # Stack to build result
        stack = []
        # Track seen letters
        seen = set()

        # Process each character
        for i, char in enumerate(s):
            # Skip if already in stack
            if char in seen:
                continue
            # Pop larger chars if they appear later
            while stack and char < stack[-1] and i < last_occurrence[stack[-1]]:
                seen.remove(stack.pop())
            stack.append(char)
            seen.add(char)

        # Build result
        return ''.join(stack)

• Lines 3-5: Map each letter to its last index.
• Lines 8-9: Initialize stack and seen set.
• Lines 12-19: Loop:
• Skip duplicates.
• Pop larger letters if safe (appear later).
• Add current letter.
• Line 21: Join stack to string.
• Time Complexity: O(n)—one pass, stack ops O(1) amortized.
• Space Complexity: O(1)—stack and set bounded by 26 letters.

This is like a letter-stacking pro—swift and sleek!

Alternative Solution: Recursive Approach

Why an Alternative Approach?

The recursive approach also solves it in O(n) time (with multiple passes), O(n) space, breaking the problem into smaller subproblems. It’s more intuitive for some, finding the smallest letter that can start the result, then recurring on the suffix. It’s like solving a word puzzle piece-by-piece—clear but less efficient!

How It Works

Divide and conquer:

• Step 1: Find smallest letter that appears last among duplicates.
• Step 2: Recur on suffix after its first occurrence.
• Step 3: Build result by prepending.

Step-by-Step Example

Example: s = "bcabc"

• Pass 1: Smallest = a, First at 2, Result = "a" + rec("bc")
• Pass 2: Smallest = b, First at 0, Result = "b" + rec("c")
• Pass 3: Smallest = c, Result = "c"
• Combine: "abc"

Code for Recursive Approach

Copy codeclass Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        if not s:
            return ""

        # Count occurrences
        count = {}
        for char in s:
            count[char] = count.get(char, 0) + 1

        # Find smallest letter that can be first
        pos = 0
        for i in range(len(s)):
            if s[i] < s[pos]:
                pos = i
            count[s[i]] -= 1
            if count[s[i]] == 0:
                break

        # Recur on suffix after first occurrence of smallest
        suffix = s[pos+1:].replace(s[pos], "")
        return s[pos] + self.removeDuplicateLetters(suffix)

• Time Complexity: O(n)—multiple passes, but O(n) total work.
• Space Complexity: O(n)—recursion stack and string ops.

It’s a recursive word crafter!

Comparing the Two Solutions

• Stack-Based (Best):
• Pros: O(n) time, O(1) space, one pass.
• Cons: Greedy logic trickier.
• Recursive (Alternative):
• Pros: O(n) time, O(n) space, intuitive breakdown.
• Cons: More memory, slower.

Stack wins for efficiency.

Additional Examples and Edge Cases

• "a": "a".
• "aaa": "a".
• "zxy": "xyz".

Both handle these perfectly.

Complexity Breakdown

• Stack-Based: Time O(n), Space O(1).
• Recursive: Time O(n), Space O(n).

Stack is leaner and faster.

Key Takeaways

• Stack-Based: Greedy stacking—brilliant!
• Recursive: Divide and conquer—clear!
• Python: Stacks and dicts shine—see [Python Basics](/python/basics).
• Order: Lexicography meets greediness.

Final Thoughts: Dedupe with Style

LeetCode 316: Remove Duplicate Letters in Python is a string manipulation masterpiece. The stack-based solution offers speed and elegance, while recursion provides a thoughtful alternative. Want more string challenges? Try LeetCode 402: Remove K Digits or LeetCode 1081: Smallest Subsequence of Distinct Characters. Ready to dedupe? Head to Solve LeetCode 316 on LeetCode and craft that smallest string today!