LeetCode 316: Remove Duplicate Letters (Monotonic Stack + Last Occurrence)
LeetCode 316StringMonotonic StackToday we solve LeetCode 316 - Remove Duplicate Letters.
Source: https://leetcode.com/problems/remove-duplicate-letters/
English
Problem Summary
Given a string s, remove duplicate letters so every letter appears once and only once, and return the lexicographically smallest possible result while keeping relative order constraints.
Key Insight
Use a monotonic increasing stack for the answer. If current char is smaller than stack top, we can pop the top only if that top appears again later, then re-add it later.
Algorithm
- Record last index of each character.
- Iterate characters left to right.
- Skip character if already in stack.
- While stack top is larger than current char and the top appears again later, pop it.
- Push current char and mark visited.
Complexity Analysis
Time: O(n).
Space: O(1) for alphabet-sized arrays (or O(k) for unique characters).
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public String removeDuplicateLetters(String s) {
int[] last = new int[26];
for (int i = 0; i < s.length(); i++) {
last[s.charAt(i) - 'a'] = i;
}
boolean[] used = new boolean[26];
StringBuilder stack = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
int idx = c - 'a';
if (used[idx]) continue;
while (stack.length() > 0) {
char top = stack.charAt(stack.length() - 1);
if (top <= c || last[top - 'a'] <= i) break;
used[top - 'a'] = false;
stack.deleteCharAt(stack.length() - 1);
}
stack.append(c);
used[idx] = true;
}
return stack.toString();
}
}func removeDuplicateLetters(s string) string {
last := make([]int, 26)
for i := 0; i < len(s); i++ {
last[s[i]-'a'] = i
}
used := make([]bool, 26)
stack := make([]byte, 0, 26)
for i := 0; i < len(s); i++ {
c := s[i]
idx := c - 'a'
if used[idx] {
continue
}
for len(stack) > 0 {
top := stack[len(stack)-1]
if top <= c || last[top-'a'] <= i {
break
}
used[top-'a'] = false
stack = stack[:len(stack)-1]
}
stack = append(stack, c)
used[idx] = true
}
return string(stack)
}class Solution {
public:
string removeDuplicateLetters(string s) {
vector<int> last(26, -1);
for (int i = 0; i < (int)s.size(); i++) {
last[s[i] - 'a'] = i;
}
vector<bool> used(26, false);
string st;
for (int i = 0; i < (int)s.size(); i++) {
char c = s[i];
int idx = c - 'a';
if (used[idx]) continue;
while (!st.empty() && st.back() > c && last[st.back() - 'a'] > i) {
used[st.back() - 'a'] = false;
st.pop_back();
}
st.push_back(c);
used[idx] = true;
}
return st;
}
};class Solution:
def removeDuplicateLetters(self, s: str) -> str:
last = {c: i for i, c in enumerate(s)}
stack = []
used = set()
for i, c in enumerate(s):
if c in used:
continue
while stack and stack[-1] > c and last[stack[-1]] > i:
used.remove(stack.pop())
stack.append(c)
used.add(c)
return ''.join(stack)var removeDuplicateLetters = function(s) {
const last = new Array(26).fill(0);
for (let i = 0; i < s.length; i++) {
last[s.charCodeAt(i) - 97] = i;
}
const used = new Array(26).fill(false);
const stack = [];
for (let i = 0; i < s.length; i++) {
const c = s[i];
const idx = c.charCodeAt(0) - 97;
if (used[idx]) continue;
while (
stack.length > 0 &&
stack[stack.length - 1] > c &&
last[stack[stack.length - 1].charCodeAt(0) - 97] > i
) {
used[stack.pop().charCodeAt(0) - 97] = false;
}
stack.push(c);
used[idx] = true;
}
return stack.join('');
};中文
题目概述
给定字符串 s，要求删除重复字母，使每个字母只出现一次，并且在满足相对顺序约束下，让结果字典序最小。
核心思路
用单调栈维护当前答案。若当前字符更小，并且栈顶字符后面还会出现，就可以弹出栈顶，后续再补回来，从而让结果更小。
算法步骤
- 先记录每个字符最后一次出现的位置。
- 从左到右扫描字符串。
- 若字符已在栈中，直接跳过。
- 当栈顶字符比当前字符大，且栈顶后续还会出现时，持续弹栈。
- 压入当前字符并标记已使用。
复杂度分析
时间复杂度：O(n)。
空间复杂度：O(1)（固定字符集）或 O(k)（不同字符数）。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public String removeDuplicateLetters(String s) {
int[] last = new int[26];
for (int i = 0; i < s.length(); i++) {
last[s.charAt(i) - 'a'] = i;
}
boolean[] used = new boolean[26];
StringBuilder stack = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
int idx = c - 'a';
if (used[idx]) continue;
while (stack.length() > 0) {
char top = stack.charAt(stack.length() - 1);
if (top <= c || last[top - 'a'] <= i) break;
used[top - 'a'] = false;
stack.deleteCharAt(stack.length() - 1);
}
stack.append(c);
used[idx] = true;
}
return stack.toString();
}
}func removeDuplicateLetters(s string) string {
last := make([]int, 26)
for i := 0; i < len(s); i++ {
last[s[i]-'a'] = i
}
used := make([]bool, 26)
stack := make([]byte, 0, 26)
for i := 0; i < len(s); i++ {
c := s[i]
idx := c - 'a'
if used[idx] {
continue
}
for len(stack) > 0 {
top := stack[len(stack)-1]
if top <= c || last[top-'a'] <= i {
break
}
used[top-'a'] = false
stack = stack[:len(stack)-1]
}
stack = append(stack, c)
used[idx] = true
}
return string(stack)
}class Solution {
public:
string removeDuplicateLetters(string s) {
vector<int> last(26, -1);
for (int i = 0; i < (int)s.size(); i++) {
last[s[i] - 'a'] = i;
}
vector<bool> used(26, false);
string st;
for (int i = 0; i < (int)s.size(); i++) {
char c = s[i];
int idx = c - 'a';
if (used[idx]) continue;
while (!st.empty() && st.back() > c && last[st.back() - 'a'] > i) {
used[st.back() - 'a'] = false;
st.pop_back();
}
st.push_back(c);
used[idx] = true;
}
return st;
}
};class Solution:
def removeDuplicateLetters(self, s: str) -> str:
last = {c: i for i, c in enumerate(s)}
stack = []
used = set()
for i, c in enumerate(s):
if c in used:
continue
while stack and stack[-1] > c and last[stack[-1]] > i:
used.remove(stack.pop())
stack.append(c)
used.add(c)
return ''.join(stack)var removeDuplicateLetters = function(s) {
const last = new Array(26).fill(0);
for (let i = 0; i < s.length; i++) {
last[s.charCodeAt(i) - 97] = i;
}
const used = new Array(26).fill(false);
const stack = [];
for (let i = 0; i < s.length; i++) {
const c = s[i];
const idx = c.charCodeAt(0) - 97;
if (used[idx]) continue;
while (
stack.length > 0 &&
stack[stack.length - 1] > c &&
last[stack[stack.length - 1].charCodeAt(0) - 97] > i
) {
used[stack.pop().charCodeAt(0) - 97] = false;
}
stack.push(c);
used[idx] = true;
}
return stack.join('');
};
Comments