DSA sheet · Stack · Greedy + Stack pattern

Remove Duplicate Letters

The second Stack + Greedy problem. The teacher solves it as a direct follow-up to Remove K Digits: there we deleted a bigger digit that came before a smaller one; here we do the same with letters, but with one extra safety check: we may only delete a letter if another copy of it comes later. She builds it in stages: a recursive brute force, a quick "keep the first copy" idea that fails, a stack that looks ahead by scanning (O(n²)), and finally the O(n) version with a last-index array and a visited array.

She also points out that the next sheet problem, Smallest Subsequence of Distinct Characters (LeetCode 1081), is worded differently but is the same problem, and leaves it for you to submit with this exact code.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · Stacks from scratch, and Greedy + Stack
• Part A · Brute force: recursion over deletions
• Part B · A tempting idea that fails: keep the first copy
• Part C · Stack + look ahead by scanning (O(n²))
• Part D · Optimal: stack + last index + visited (O(n))
• Part E · Revision page

Part 0 · Before starting

What is a stack?

A stack is a pile: you add on the top (push), look at the top (peek), and remove from the top (pop). The last thing in is the first thing out: LIFO (Last In, First Out).

stack = []
stack.append('b')     # push
top = stack[-1]       # peek (don't remove)
x = stack.pop()       # pop (remove the top)
if stack: ...         # empty check: [] counts as False

We write a stack left = bottom, right = top. Always check that the stack is not empty before stack[-1] or stack.pop(), or Python raises IndexError.

Lexicographic order ("dictionary order")

"Lexicographically smallest" means "the one that comes first in a dictionary". Compare two strings letter by letter from the left; the first letter that differs decides. "abc" < "bca" because a < b at the very first position. Python's < on strings does exactly this, and so does > on single letters ('a' < 'b' < … < 'z').

Greedy + Stack, and what's new here

The pattern from Remove K Digits: walk left to right; before pushing a new item, pop the top while it is bigger than the new item. Popping a bigger item lets the smaller one move further left, and a smaller letter further left makes the whole string smaller. The stack stays mostly increasing (a monotonic stack), and it remembers the best answer we can build from the part we've read so far.

New in this problem: every distinct letter must appear exactly once in the answer. So we can't pop a letter just because it is bigger. We may pop it only if another copy of it appears later, so it can come back in a better spot. Otherwise popping it would lose that letter forever.

for i, x in enumerate(s):
    if x already in stack: skip it
    while stack and stack[-1] > x and stack[-1] appears after i:
        stack.pop()        # safe: we will meet it again later
    stack.append(x)

Part A · Brute force: recursion over deletions

LeetCode 316 (same as LeetCode 1081)

1The question in simple words

You get a string s of lowercase letters. Remove the extra copies so that each letter appears exactly once. You can't reorder anything; you only choose which copy of each letter to keep. Among all the ways to do that, return the one that is lexicographically smallest.

You could also remove the later b and c and get "bca". That also has each letter once, but "abc" comes first in the dictionary, so "abc" is the answer. Second example: "cbacdcbc" → "acdb".

2What the constraints tell us

• 1 ≤ s.length ≤ 10⁴ → the teacher reads this to judge any brute force: an exponential method is hopeless, and even O(n²) = 10⁸ is borderline.
• s has only lowercase English letters → just 26 possible letters. This matters a lot in Part D: we can use arrays of size 26 instead of hash maps.

3Intuition: why counting isn't enough

A first thought is to count each letter. A count above 1 tells you which letters have duplicates (b and c in "bcabc"). But it doesn't tell you which copy to delete: the first b or the second? That depends on what comes after each copy, and a count knows nothing about positions. So frequency alone doesn't solve it.

The brute-force idea is simple: try every way of deleting duplicates, and keep the smallest string that has all its letters unique.

4Building the logic

Write a recursive function solve(t):

• If every letter of t is already unique → it's a valid candidate. Compare it with the best so far and keep the smaller one. Stop here: deleting more would make it too short.
• Otherwise, for every position i, delete t[i] and call solve on the shorter string.

On "bcabc": deleting the first b gives "cabc" (still has two c's) → deleting a c gives "abc" ✓, the first answer stored. Other branches later give "bca", "cab" and so on; each is compared with "abc" and loses.

5Approach steps

1. Start with best = None and call solve(s).
2. In solve(t): if all letters are unique → update best if t is smaller; return.
3. Else for each i where t[i] still appears more than once → solve(t without index i).
4. Return best.

6Code (Python)

class Solution:
    def removeDuplicateLetters(self, s):
        self.best = None
        self.solve(s)
        return self.best

    def solve(self, t):
        if len(set(t)) == len(t):                  # all letters unique
            if self.best is None or t < self.best:
                self.best = t
            return
        for i in range(len(t)):
            if t.count(t[i]) > 1:                  # only delete a repeated letter
                self.solve(t[:i] + t[i + 1:])

7Code line by line

8Dry run (top of the recursion tree for "bcabc")

solve("bcabc")                 b and c repeat
├─ delete b@0 → "cabc"
│   ├─ delete c@0 → "abc"   unique → best = "abc"
│   └─ delete c@3 → "cab"   unique, "cab" > "abc" → keep "abc"
├─ delete c@1 → "babc"
│   ├─ delete b@0 → "abc"   same as best
│   └─ delete b@2 → "bac"   "bac" > "abc"
├─ delete b@3 → "bcac"
│   ├─ delete c@1 → "bac"
│   └─ delete c@3 → "bca"
└─ delete c@4 → "bcab"
    ├─ delete b@0 → "cab"
    └─ delete b@3 → "bca"
answer: "abc"

9Complexity & remember

• Time: exponential. Each call branches into up to n more calls, so the tree explodes. The teacher sums it up as the usual recursion cost, about 2ⁿ. With n up to 10⁴ this would never finish (TLE). She says it is so slow that it isn't even worth coding in an interview, just worth explaining.
• Space: O(n) recursion depth, plus the strings in each frame.

Part B · A tempting idea that fails: keep the first copy

1The idea

Walk left to right. If a letter hasn't been seen yet, add it to the answer; if it has, skip it. This removes all duplicates in one pass.

2Run it on "bcabc"

We get "bca", but the answer is "abc". The duplicates are gone, but nothing makes the result smallest. Once b and c were placed, the small 'a' had to sit behind them.

3The fix comes from Remove K Digits

The teacher recalls the previous problem. There, while reading 1, 4 we couldn't decide anything yet, because the digits were going up. When 3 arrived after 4, we knew deleting the 4 makes the number smaller, so we went back and deleted it. Give letters numbers to see the same picture here: a = 1, b = 2, c = 3, d = 4. "bca" is 2, 3, 1. As long as the letters rise (2, 3) we keep them. When 'a' (1) arrives, everything bigger before it (b, c) is worth deleting.

But there's a catch: in Remove K Digits we could delete any digit while k > 0. Here we must keep one copy of every letter. We may only go back and delete b and c if we are sure another b and another c come later. In "bcabc", they do (indices 3 and 4), so deleting them is safe. Parts C and D are two ways of answering "does it come later?".

Part C · Stack + look ahead by scanning (O(n²))

1The question (same)

Same problem. Now we use the Greedy + Stack idea with a direct check: "does this letter appear later?"

2What the constraints tell us

n ≤ 10⁴, so an O(n²) method does about 10⁸ steps. The teacher calls it possible but slow. It's a stepping stone to Part D.

3Intuition

Stand at position i with the new letter ch. Before popping the top, walk ahead from i + 1 and look for another copy of the top letter. If you find one, the pop is safe.

4Building the logic

• Already in the stack? Skip it. Otherwise, in "bcabc", after building "abc" we'd later push the second b again. (Why skipping is always right is explained in Part D.)
• Pop condition: the stack isn't empty, the top > ch, and the top appears somewhere after i.
• When we pop a letter, it's no longer in the stack, so remove it from the "in stack" set. That way it can be pushed again when we meet its later copy.

5Approach steps

1. For each index i and letter ch: if ch is in the stack, skip.
2. While the top > ch and the top appears after i (found by scanning) → pop it and remove it from the set.
3. Push ch and add it to the set.
4. Join the stack.

6Code (Python)

class Solution:
    def removeDuplicateLetters(self, s):
        stack = []
        in_stack = set()
        for i, ch in enumerate(s):
            if ch in in_stack:
                continue
            # s.find(x, i + 1) scans to the right: -1 means "not found"
            while stack and stack[-1] > ch and s.find(stack[-1], i + 1) != -1:
                in_stack.remove(stack.pop())
            stack.append(ch)
            in_stack.add(ch)
        return ''.join(stack)

7Code line by line

8Dry run

The steps are identical to Part D's dry run below. The only difference is how "appears later" is answered: here by scanning to the right, there by one array lookup.

9Complexity & remember

• Time O(n²): every pop check can scan the rest of the string. The teacher's words: an extra O(n) inside the O(n) loop → O(n²).
• Space O(n) for the stack (at most 26 letters, in fact).

Part D · Optimal: stack + last index + visited (O(n))

1The question (same)

Remove duplicates, keep each letter once, and get the lexicographically smallest result, in one pass.

2What the constraints tell us

• Only 26 lowercase letters → two small arrays of size 26 are enough for all the bookkeeping.
• n ≤ 10⁴ → O(n) is very comfortable.

3Intuition: write down where each letter appears for the last time

"Does letter x appear after position i?" is the same as "is the last position of x bigger than i?". So, before the main loop, walk the string once and store the last index of every letter. For "bcabc":

The teacher builds it step by step: b at 0, then c at 1, a at 2, then b again at 3 (overwrite 0 with 3), then c at 4 (overwrite 1 with 4). Now "does c appear after index 2?" is one lookup: last['c'] = 4 > 2 → yes.

4Building the logic

Why the greedy pop is safe here

Say the top is letter t, the new letter is c, t > c, and t's last index is after i. If we keep t where it is, the answer has t at that position. If we pop it, c takes that position. All letters before it are the same, and c < t at the first position that differs, so the string is smaller. And we haven't lost t, because we'll meet it again later and push it then. Bigger letter on top + it appears again later → pop it.

If t does not appear later, popping it would remove the last chance to include t, so the answer would be missing a letter (invalid). Then we stop popping, even if t > c. That's why we can't simply copy the Remove K Digits loop.

The visited array: skip letters already in the stack

The teacher raises this while walking forward: if a letter is already sitting in the stack and another copy of it arrives, pushing it again would put the letter in the answer twice. For example, in "cbacdcbc" the stack is [a, c, d] when the c at index 5 arrives, so that c must be skipped. To know this in O(1), keep visited[letter] = True while that letter is in the stack. You could also use a set; she says any "is it already there?" structure works.

Un-mark when you pop (her key point)

When 'a' arrives in "bcabc", b and c are already marked visited. We pop them. If we forget to set visited back to False, then when the later b and c arrive, we'd think "already in the stack" and skip them, and the answer would be just "a". So every pop must also do visited[top] = False.

Why arrays and not a HashMap

The letters are only 'a' to 'z', a fixed size of 26. An array indexed by ord(ch) - ord('a') (Java: ch - 'a') gives 0 for 'a', 1 for 'b', … 25 for 'z'. Arrays avoid the hashing work a map does on every lookup, so the teacher prefers an int array for last index and a boolean array for visited.

As in Remove K Digits, her Java code uses a StringBuilder as the stack because Java's Stack class is slower. In Python we use a list and ''.join.

5Approach steps

1. First pass: last[letter] = the last index where it appears.
2. Make visited = 26 × False and an empty stack.
3. For each index i and letter ch: if visited[ch] → skip.
4. While the stack isn't empty, the top > ch, and last[top] > i → pop the top and set visited[top] = False.
5. Push ch and set visited[ch] = True.
6. Return the stack joined into a string.

6Code (Python)

class Solution:
    def removeDuplicateLetters(self, s):
        last = [0] * 26                       # last index of each letter
        for i, ch in enumerate(s):
            last[ord(ch) - ord('a')] = i

        visited = [False] * 26                # is this letter in the stack now?
        stack = []
        for i, ch in enumerate(s):
            idx = ord(ch) - ord('a')
            if visited[idx]:
                continue                      # already placed: skip this copy
            # bigger letter on top AND it appears again later: drop it
            while stack and stack[-1] > ch and last[ord(stack[-1]) - ord('a')] > i:
                top = stack.pop()
                visited[ord(top) - ord('a')] = False   # it can come back later
            stack.append(ch)
            visited[idx] = True
        return ''.join(stack)

7Code line by line

8Dry run

Example 1: s = "bcabc" (last: a = 2, b = 3, c = 4)

Answer "abc" ✓. If we had forgotten to un-mark b and c at i = 2, both would be skipped at i = 3 and 4, and we'd return "a".

Example 2: s = "cbacdcbc" (last: a = 2, b = 6, c = 7, d = 4)

Answer "acdb" ✓. Row 6 is the important one: b is smaller than d, but d has no copy left, so popping it would lose d. The "appears later" check is what makes this problem different from Remove K Digits.

9Complexity & remember

• Time O(n): one pass to fill last, one pass to build the stack. That's 2n by the teacher's count, which is linear. The inner while loop doesn't change this: there are at most n pushes, and each pushed letter can be popped at most once, so all the pops together are at most n.
• Space: last and visited are 26 each (2 × 26), which is constant. The teacher counts the StringBuilder/stack as O(n) for holding the answer. (Since every letter appears at most once in the stack, it never holds more than 26 letters, so the extra space is really O(1) apart from the output.)

Part E · Revision page

s = Solution()
print(s.removeDuplicateLetters("bcabc"))      # abc
print(s.removeDuplicateLetters("cbacdcbc"))   # acdb
print(s.removeDuplicateLetters("a"))          # a
print(s.removeDuplicateLetters("aaaa"))       # a
print(s.removeDuplicateLetters("abcd"))       # abcd
print(s.removeDuplicateLetters("dcba"))       # dcba
print(s.removeDuplicateLetters("ecbacba"))    # eacb

Based on this video: Remove Duplicate Letters | Stack + Greedy