一道数组去重的算法题把我整不会了

1081. 不同字符的最小子序列 https://leetcode.cn/problems/smallest-subsequence-of-distinct-characters

1081. Smallest Subsequence of Distinct Characters https://leetcode.com/problems/smallest-subsequence-of-distinct-characters

316. 去除重复字母 https://leetcode.cn/problems/remove-duplicate-letters

316. Remove Duplicate Letters https://leetcode.com/problems/remove-duplicate-letters

Info

已完成网站教程、网站习题、配套插件中所有多语言代码的校准，解决了之前 chatGPT 翻译可能出错的问题~

读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：

LeetCode	Difficulty
1081. Smallest Subsequence of Distinct Characters	🟠
316. Remove Duplicate Letters	🟠

Prerequisites

Before reading this article, you should learn:

• Principles of Queues/Stacks
• Monotonic Stack Principles and Implementation

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 <= 104
• s consists 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:

loading...