Skip to main content
Talentd

Lexicographically Smallest String After Deleting Duplicate Characters - Solution & Explanation

HardHash TableStringStackGreedy8 min readAsked at: Meta, Paytm
Practice this problem

Problem Statement

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 <= 105
  • s contains lowercase English letters only.

Approach Overview

Problem Overview: Given a string, remove duplicate characters so every character appears exactly once while keeping the result lexicographically smallest. The relative order of characters must remain valid based on the original string.

Approach 1: Brute Force with Backtracking (Exponential Time, O(2^n) time, O(n) space)

Generate all subsequences that contain unique characters and keep the lexicographically smallest valid result. Use a set to ensure characters appear only once in the candidate string and recursively explore include/exclude decisions. Each subsequence must also maintain original ordering since it's derived directly from the input. This approach demonstrates the problem constraints but quickly becomes infeasible for larger strings because the search space grows exponentially.

Approach 2: Greedy Monotonic Stack (Optimal) (O(n) time, O(n) space)

The optimal solution uses a stack combined with greedy decisions. First record the last occurrence index of each character using a hash table. Iterate through the string and maintain a stack representing the current result. If the current character is smaller than the stack's top and the top character appears later again in the string, pop it to make the result lexicographically smaller. Push the current character if it hasn't already been used. A visited set ensures each character appears once, and the stack naturally forms the smallest lexicographic sequence.

This works because characters that appear again later can safely be removed from the stack if a smaller character appears earlier in the result. The stack therefore behaves like a monotonic stack that maintains the best possible lexicographic ordering while guaranteeing every character is included exactly once.

Recommended for interviews: Interviewers expect the greedy monotonic stack solution with last-occurrence tracking. Brute force demonstrates understanding of the constraint space, but the O(n) stack approach shows strong algorithmic reasoning and familiarity with stack-based greedy optimization patterns.

Solution

We can use a stack stk to store the characters of the result string, and a hash table cnt to record the number of occurrences of each character in string s.

First, we initialize cnt to count the occurrences of each character in string s. Then, we iterate through each character c in string s:

  • If the stack is not empty, the top character of the stack is greater than c, and the top character will appear again in string s, we pop the top character and decrement its count in cnt.
  • Push character c into the stack.

Finally, if there are duplicate characters in the stack, we continue to pop the top character until the count of the top character in cnt is 1.

The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the string s.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force BacktrackingO(2^n)O(n)Understanding the full search space or validating small inputs
Greedy Monotonic StackO(n)O(n)Optimal solution for production and interviews; works for large strings

Video Solution

Lexicographically Smallest String After Deleting Duplicate Characters 🔥 LeetCode 3816 | Optimal • Study Placement • 548 views views

Watch 3 more video solutions →

Frequently Asked Questions

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.
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.
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.
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.
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.
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.

Ready to solve this problem?

Practice Lexicographically Smallest String After Deleting Duplicate Characters with our built-in code editor and test cases.

Practice on FleetCode
Previous

Remove Duplicate Letters