316. Remove Duplicate Letters

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• offer
• 多多！

Problem

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.

Note: This question is the same as 1081: https://leetcode.com/problems/smallest-subsequence-of-distinct-characters/

Example 1:

Input: s = "bcabc"
Output: "abc"
Example 2:

Input: s = "cbacdcbc"
Output: "acdb"

Note: This question is the same as 1081: https://leetcode.com/problems/smallest-subsequence-of-distinct-characters/

Code

class Solution {
    private int findMinLastPos(HashMap<Character, Integer> map){
        int res = Integer.MAX_VALUE;
        for(int num : map.values()){
            res = Math.min(res, num);
        }

        return res;
    }

    public String removeDuplicateLetters(String s) {
        if(s == null || s.length() == 0) return s;
        // 0 1 2 3 4 5 6 7
        // c b a c d c b c
        // map
        // a : 2
        // c : 7
        // d : 4
        // b : 6
        HashMap<Character, Integer> map = new HashMap<>();

        // 每个元素只保存最后的位置
        // 它必须在这个位置之前出现, 否则就没法出现了
        for(int i = 0; i < s.length(); i++){
            map.put(s.charAt(i), i);
        }

        // 一共几种字母
        char[] res = new char[map.size()];

        int start = 0;
        // 找到map中的最小值
        // a : 2
        // end = 2
        int end = findMinLastPos(map);

        // 每次往结果中加入一个, 同时更新map和end
        for(int i = 0; i < res.length; i++){
            char minChar = 'z' + 1;
            // 找到当前片段中的最小字符
            for(int k = start; k <= end; k++){
                // map中还有这个字符, 表示res中还没有
                if(map.containsKey(s.charAt(k)) && s.charAt(k) < minChar){
                    minChar = s.charAt(k);
                    start = k + 1;
                }
            }

            res[i] = minChar;
            map.remove(minChar);
            // 如果这个字符是map中的最小字符, 需要更新map
            if(s.charAt(end) == minChar){
                end = findMinLastPos(map);
            }
        }

        return new String(res);
    }
}

class Solution:
    def findMinLastPos(self, mm) -> int:
        min_pos = float("inf")
        for key in mm:
            min_pos = min(min_pos, mm[key])

        return min_pos


    def smallestSubsequence(self, s: str) -> str:
        mm = {c: i for i, c in enumerate(s)}

        start = 0
        end = self.findMinLastPos(mm)

        res = [0] * len(mm)

        for i in range(len(res)):
            min_char = chr(ord('z') + 1)
            for k in range(start, end + 1):
                if ord(s[k]) < ord(min_char) and s[k] in mm:
                    min_char = s[k]
                    start = k + 1

            res[i] = min_char

            del mm[min_char]

            if s[end] == min_char:
                end = self.findMinLastPos(mm)

        return "".join(res)