每日一题：Leetcode-316 去除重复字母

力扣题目

解题思路

java代码

力扣题目：

给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的

字典序

最小（要求不能打乱其他字符的相对位置）。

示例 1：

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

示例 2：

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

提示：

• 1 <= s.length <= 104
• s 由小写英文字母组成

解题思路：

算法原理：
这道题的目的是从给定的字符串中移除重复的字母，使得结果字符串的字符顺序保持最小字典序，且每个字符最多出现一次。

思路：

1. 首先创建两个辅助数组，vis 数组用于标记字符是否已在结果字符串中，num 数组用于记录每个字符在原始字符串中剩余的出现次数。
2. 遍历原始字符串，对于每个字符：
   • 如果该字符尚未在结果字符串中，且结果字符串末尾的字符大于当前字符，并且末尾字符在后续还有出现机会（即其剩余数量大于 0），则将末尾字符从结果字符串中移除，并更新其在 vis 数组中的标记。
   • 将当前字符标记为已在结果字符串中，并添加到结果字符串中。
   • 减少当前字符在 num 数组中的剩余数量。

代码分析：

• 首先通过遍历字符串初始化 num 数组。
• 然后通过另一个循环处理每个字符，进行上述的条件判断和操作。

时间复杂度：O（n），其中 n 是字符串 s 的长度。需要对字符串进行一次遍历。

空间复杂度：O（26），用于存储 vis 和 num 数组，空间复杂度为常数级别。

java代码：

package com.example.lib;

public class Leetcode316 {
    public static void main(String[] args) {
        String s = "cbacdcbc";
        System.out.println(new Leetcode316().removeDuplicateLetters(s));
    }
    public String removeDuplicateLetters(String s) {
        boolean[] vis = new boolean[26];
        int[] num = new int[26];
        for (int i = 0; i < s.length(); i++) {
            num[s.charAt(i) - 'a']++;
        }

        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (!vis[ch - 'a']) {
                while (sb.length() > 0 && sb.charAt(sb.length() - 1) > ch) {
                    if (num[sb.charAt(sb.length() - 1) - 'a'] > 0) {
                        vis[sb.charAt(sb.length() - 1) - 'a'] = false;
                        sb.deleteCharAt(sb.length() - 1);
                    } else {
                        break;
                    }
                }
                vis[ch - 'a'] = true;
                sb.append(ch);
            }
            num[ch - 'a'] -= 1;
        }
        return sb.toString();
    }
}

更多详细内容同步到公众号，感谢大家的支持！

每天都会给刷算法的小伙伴推送明日一题，并且没有任何收费项