What is the best approach for Lexicographically Smallest String After Deleting Duplicate Characters?

The optimal approach uses a greedy monotonic stack with last-occurrence tracking. While iterating through the string, characters are pushed to a stack while maintaining lexicographic order. If a larger character appears earlier and also occurs later in the string, it can be safely popped to produce a smaller result. This algorithm runs in O(n) time with O(n) space.

What data structure is used in Lexicographically Smallest String After Deleting Duplicate Characters?

The primary data structure is a stack used as a monotonic structure to maintain lexicographic order. A hash table tracks the last occurrence of each character, and a set tracks which characters are already included in the result.

What is the time complexity of Lexicographically Smallest String After Deleting Duplicate Characters?

The optimal monotonic stack solution runs in O(n) time where n is the length of the string. Each character is pushed and popped from the stack at most once. Space complexity is O(n) due to the stack, visited set, and last-occurrence map.

Description Hints 6 Solution Video 27:49

3816. Lexicographically Smallest String After Deleting Duplicate Characters

Q: Is Lexicographically Smallest String After Deleting Duplicate Characters easy or hard?

The problem is considered Hard because it requires combining greedy decisions with a monotonic stack and last-occurrence tracking. Many candidates initially attempt brute force or sorting-based approaches before recognizing the linear-time greedy pattern.

Q: Lexicographically Smallest String After Deleting Duplicate Characters Python/Java solution

Implement the greedy monotonic stack algorithm. Track the last index of each character, maintain a stack for the result, and a visited set to avoid duplicates. The same logic works across Python, Java, C++, Go, and TypeScript with O(n) time complexity.

Q: How to solve Lexicographically Smallest String After Deleting Duplicate Characters in O(n)?

Store the last index of each character, then iterate through the string while maintaining a stack and a visited set. If the current character is smaller than the stack top and the stack top appears later again, pop the stack. Push the current character if it hasn't already been used. This greedy process guarantees the smallest lexicographic result in linear time.

Q: Is Lexicographically Smallest String After Deleting Duplicate Characters asked at Google/Amazon/Meta?

Variants of this problem appear in interviews at companies like Google, Amazon, and Meta because it tests greedy reasoning, stack usage, and string manipulation. It is closely related to classic problems such as "Remove Duplicate Letters" that are commonly used in technical interviews.

Hard20.9% acceptance2 companies

You are given a string s that consists of lowercase English letters.

You can perform the following operation any number of times (possibly zero times):

Choose any letter that appears at least twice in the current string s and delete any one occurrence.

Return the lexicographically smallest resulting string that can be formed this way.

Example 1:

Input: s = "aaccb"

Output: "aacb"

Explanation:

We can form the strings "acb", "aacb", "accb", and "aaccb". "aacb" is the lexicographically smallest one.

For example, we can obtain "aacb" by choosing 'c' and deleting its first occurrence.

Example 2:

Input: s = "z"

Output: "z"

Explanation:

We cannot perform any operations. The only string we can form is "z".

Constraints:

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

Asked at 2 companies

Paytm Meta

Topics

Hints open one at a time

Hint 1

Solve greedily.

Hint 2

Each distinct letter must appear at least once in the final string.

Hint 3

For each letter, maintain a deque of its positions.

Hint 4

At each step, try letters from 'a' to 'z' and pick the smallest letter whose earliest position lies within a safe window.

Hint 5

Do not pick an occurrence if choosing it would make some other letter impossible to keep.

Hint 6

Mark positions as used and repeat, always minimizing the next chosen character.

27:49

Still stuck?Read the written solution, or watch a walkthrough.

Open solution