Removing Duplicates from an Array (Hard Version)
Note
Now all the plugins has supported English. I'm still improving the website...
This article will resolve
| LeetCode | Difficulty |
|---|---|
| 1081. Smallest Subsequence of Distinct Characters | 🟠 |
| 316. Remove Duplicate Letters | 🟠 |
Prerequisites
Before reading this article, you should learn:
Regarding deduplication algorithms, it shouldn't be too difficult, right? Just insert elements into a hash set, and you're done?
At most, you might face some constraints, like how to deduplicate an ordered array in place. We covered this in a previous article Mastering Array Problems with Two-Pointer Technique.
The problem discussed in this article is probably the most challenging in deduplication algorithms. Once you understand this, you won't need to worry about array deduplication problems anymore.
This is LeetCode problem #316, "Remove Duplicate Letters," described as follows:
316. Remove Duplicate Letters | LeetCode |
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 <= 104sconsists of lowercase English letters.
Note: This question is the same as 1081: https://leetcode.com/problems/smallest-subsequence-of-distinct-characters/
The solution to this problem is identical to that of problem #1081, "Smallest Subsequence of Distinct Characters." You can directly use the solution code from this problem to solve #1081 as well.
The problem requirements can be summarized into three points:
Requirement 1: Deduplicate the characters.
Requirement 2: The order of characters in the deduplicated string must not disrupt the relative order of characters in s.
Requirement 3: Among all deduplicated strings that meet the above requirement, the one with the smallest lexicographical order should be the final result.
Among these three requirements, the third one might be a bit tricky to understand. Let's take an example.
For an input string s = "babc", there are two possible deduplicated strings that maintain the relative order: "bac" and "abc". However, our algorithm should return "abc" because it has a smaller lexicographical order.
Logically, if we want an ordered result, we should sort the original string, right? But sorting would disrupt the original order of characters in s, which seems contradictory.
Actually, we will borrow the idea of the "Monotonic Stack" from a previous article Monotonic Stack Solution Framework. Don't worry if you haven't read it; you'll understand soon.
Let's temporarily ignore Requirement 3 and use a stack to implement Requirements 1 and 2. You'll see why we use a stack shortly: