Given a string s, remove duplicate letters so that every letter appears once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.
Example 1:
Input: s = "bcabc" Output: "abc"
Example 2:
Input: s = "cbacdcbc" Output: "acdb"
Constraints:
1 <= s.length <= 104s consists of lowercase English letters.
Note: This question is the same as 1081: https://leetcode.com/problems/smallest-subsequence-of-distinct-characters/
This approach uses a stack to build the resultant string such that it is the smallest lexicographical order. We will also use an array to keep count of each character’s frequency and a boolean array to track the characters that have been added to the stack. As we iterate over each character, we decide whether to add it to the stack or skip it based on the frequency and lexicographical conditions.
The code iterates through the string, keeping track of character frequencies and deciding whether to add each character to a stack based on lexicographical ordering and frequency constraints. Characters are popped from the stack if they have occurred later, are greater than the current character, and are not the last occurrence.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the length of the string, as each character is pushed and popped from the stack at most once.
Space Complexity: O(1), because the stack contains at most 26 characters, and other auxiliary data structures are of constant size.
This approach focuses on iteratively constructing the result string while ensuring that the result remains lexicographically smallest by checking each character and including it in the result only if it meets certain frequency and order criteria.
In this solution, a character set is updated via a general loop to progressively add elements to the result string. This method leverages frequency checks of character availability while ensuring characters are not redundant in the result.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the length of the input string.
Space Complexity: O(1), considering character storage is bounded to a maximum of 26.
| Approach | Complexity |
|---|---|
| Approach 1: Greedy and Stack | Time Complexity: O(n), where n is the length of the string, as each character is pushed and popped from the stack at most once. |
| Approach 2: Iterative with Result String Construction | Time Complexity: O(n), where n is the length of the input string. |
Remove Duplicate Letters | Leetcode #316 • Techdose • 30,125 views views
Watch 9 more video solutions →Practice Remove Duplicate Letters with our built-in code editor and test cases.
Practice on FleetCode