DSA Remove Duplicate Letters

The problem

Remove Duplicate Letters keeps exactly one copy of each letter in a string. The kept letters form the smallest result in lexicographic order. Lexicographic order is the dictionary order of strings, compared letter by letter from the left.

The answer in this article is that smallest string. Every distinct letter of the input appears once in it. The result order is a new order, not the order the letters were first seen.

for s in ['bcabc', 'cbacdcbc', 'aaaa', 'zyx']:
    print('input:', s, 'distinct letters:', len(set(s)))

The first case answers abc. The second answers acdb, which is not the sorted order of its letters. That gap between sorted and achievable is the heart of the problem.

Intuition: sort the distinct letters

The first idea collects the distinct letters and sorts them. Sorting gives the smallest order in the abstract. The input may simply never allow that order.

The trap is the string cbacdcbc. Its sorted distinct letters spell abcd. No subsequence of the input spells abcd, because d sits before the last b and c, so a result starting a, then b, then c, then d cannot be traced in order.

s = 'cbacdcbc'
print('sorted distinct letters:', ''.join(sorted(set(s))))
pos = -1
ok = True
for ch in 'abcd':
    nxt = s.find(ch, pos + 1)
    if nxt == -1:
        ok = False
        print('letter', ch, 'not found after index', pos)
        break
    pos = nxt
print('abcd is a subsequence:', ok)

A result must be a subsequence of the input, meaning its letters appear in the input in the same order, not necessarily side by side. The smallest answer is the smallest subsequence that uses each distinct letter once. That constraint shapes the whole solution.

Brute force: test every subsequence that keeps one copy each

The brute force enumerates every subsequence of the input. It keeps those holding each distinct letter exactly once. The smallest kept subsequence is the answer.

import itertools
def brute(s):
    distinct = set(s)
    tested = [0]
    best = None
    indices = range(len(s))
    for r in range(len(s) + 1):
        for combo in itertools.combinations(indices, r):
            tested[0] += 1
            sub = ''.join(s[i] for i in combo)
            if set(sub) == distinct and len(sub) == len(distinct):
                if best is None or sub < best:
                    best = sub
    return best, tested[0]
result, tested = brute('bcabc')
print('result:', result)
print('subsequences tested:', tested)

A five-letter string already has 32 subsequences. Each added letter doubles that count. The optimal stack builds the same answer in one walk, with each letter pushed and popped at most once.

The optimal solution: a rising stack that pops only safe letters

A monotonic stack is a stack whose letters stay in rising order, and a larger letter on top is popped only when it appears again later in the string. That one sentence is the whole method.

The last occurrence table records the final index of each letter. The in-stack set records which letters are already placed, so a repeat of a placed letter is skipped. Each distinct letter enters the final stack exactly once.

def smallest(s):
    last = {}
    for index, ch in enumerate(s):
        last[ch] = index
    stack = []
    in_stack = set()
    pushes = [0]
    pops = [0]
    skips = [0]
    for index, ch in enumerate(s):
        if ch in in_stack:
            skips[0] += 1
            continue
        while stack and stack[-1] > ch and last[stack[-1]] > index:
            in_stack.remove(stack.pop())
            pops[0] += 1
        stack.append(ch)
        in_stack.add(ch)
        pushes[0] += 1
    return ''.join(stack), pushes[0], pops[0], skips[0]
for s in ['bcabc', 'cbacdcbc', 'aaaa', 'zyx']:
    result, pushes, pops, skips = smallest(s)
    print('input:', s, 'result:', result, 'pushes:', pushes, 'pops:', pops, 'skips:', skips)

Every case from the start of the article is answered. The string zyx keeps its order, because no letter in it ever returns later, so no pop is ever safe. The string aaaa collapses to a single a.

Walkthrough: reducing bcabc step by step

The walk shows each push, pop, and skip for the first case. The state is the stack after each letter. A pop prints its reason, that the popped letter returns later.

s = 'bcabc'
last = {}
for index, ch in enumerate(s):
    last[ch] = index
stack = []
in_stack = set()
for index, ch in enumerate(s):
    if ch in in_stack:
        print('skip', ch, 'already placed')
        continue
    while stack and stack[-1] > ch and last[stack[-1]] > index:
        gone = stack.pop()
        in_stack.remove(gone)
        print('pop', gone, 'it returns later')
    stack.append(ch)
    in_stack.add(ch)
    print('push', ch, 'stack:', ''.join(stack))
print('result:', ''.join(stack))

Both opening letters pop when a arrives, because both return later. The stack then rebuilds as abc from the later copies. The result is read straight off the final stack.

Complexity

Each letter is pushed at most once and popped at most once, so the walk costs O(n) time for a string of length n. Its space is at most one stack entry and one table entry per distinct letter.

for n in [5, 8, 16]:
    print('length', n, '- stack pushes at most:', n, ' brute subsequences:', 2 ** n)

At length 16 the walk pushes at most 16 letters. The brute force would test 65536 subsequences. The push and pop counts printed in the optimal section stay well under the length of each input.

Edge cases and pitfalls

Popping a larger letter that never returns is the classic mistake. That letter is then lost for good, and the result misses a distinct letter entirely. The last occurrence check is what makes a pop safe, and it is never optional.

An empty string gives an empty result. A string already in rising order with no repeats returns itself unchanged, because no letter on its stack is ever larger than the next letter.

def smallest(s):
    last = {}
    for index, ch in enumerate(s):
        last[ch] = index
    stack = []
    in_stack = set()
    for index, ch in enumerate(s):
        if ch in in_stack:
            continue
        while stack and stack[-1] > ch and last[stack[-1]] > index:
            in_stack.remove(stack.pop())
        stack.append(ch)
        in_stack.add(ch)
    return ''.join(stack)
print('empty:', repr(smallest('')))
print('single:', smallest('q'))
print('rising:', smallest('abcd'))
print('falling, no repeats return:', smallest('zyx'))
print('all same:', smallest('aaaa'))

The falling case returns itself, and that answer is correct. No pop in it is safe, so the stack never shrinks. Safety, not smallness alone, decides every pop.