去除重复字母

题目链接描述示例初始代码模板代码

题目链接

https://leetcode-cn.com/problems/remove-duplicate-letters/

描述

给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。 注意：该题与 1081 https://leetcode-cn.com/problems/smallest-subsequence-of-distinct-characters 相同 提示： 1 <= s.length <= 104 s 由小写英文字母组成

示例

示例 1：

输入：s = "bcabc" 输出："abc"

示例 2：

输入：s = "cbacdcbc" 输出："acdb"

初始代码模板

class Solution { public String removeDuplicateLetters(String s) { } }

代码

推荐题解：https://labuladong.gitbook.io/algo/shu-ju-jie-gou-xi-lie/dan-tiao-zhan-qu-zhong 注意题目的三个点就好： 1.去重 2.保留相对位置 3.满足前两个条件的情况下字典序最小

class Solution { public String removeDuplicateLetters(String s) { LinkedList<Character> stack = new LinkedList<>(); int[] count = new int[256]; for (int i = 0; i < s.length(); i++) { count[s.charAt(i)]++; } boolean[] inStack = new boolean[256]; for (int i = 0; i < s.length(); i++) { char c = s.charAt(i); count[c]--; if (inStack[c]) continue; while (!stack.isEmpty() && stack.peek() > c) { if (count[stack.peek()] == 0) { break; } inStack[stack.pop()] = false; } stack.push(c); inStack[c] = true; } StringBuilder sbu = new StringBuilder(); while (!stack.isEmpty()) { sbu.append(stack.pop()); } return sbu.reverse().toString(); } }