1081. Smallest Subsequence of Distinct Characters

JIAKAOBO

LeetCode

感谢赞助!

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

Problem

Return the lexicographically smallest subsequence of s that contains all the distinct characters of s exactly once.

Note: This question is the same as 316: https://leetcode.com/problems/remove-duplicate-letters/

Example 1:

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

Example 2:

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

Code

same as 316

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)