Search⌘ K
AI Features
Home
Courses
Grokking the Coding Interview Patterns

Solution: Remove Duplicate Letters

Explore how to solve the problem of removing duplicate letters from a lowercase string while ensuring the result is lexicographically smallest. This lesson guides you through a greedy algorithm using a stack, frequency map, and visited set. You will understand how to efficiently manage character order and presence to generate the final string. The approach runs in linear time and uses constant auxiliary space, making it practical for coding interviews and string manipulation challenges.

We'll cover the following...

Statement

You are given a string, s, consisting only of lowercase English letters. Your task is to remove duplicate letters so that:

  1. Each letter appears only once in the resulting string.

  2. The resulting string is the smallest in lexicographical order among all possible results that satisfy the above condition.

Return the final string.

A string, a, is considered lexicographically smaller than string b if:

  • In the first position where they differ, the character in a appears earlier in the alphabet than in b.

  • If a is a ...