LeetCode

删除重复字符并且得到最大字符串

2022-02-18  本文已影响0人  Billsion

描述:
给定一个字符串S,选择至少出现2次的任何字符并删除其中任何一个,重复操作,直到没有重复的字符串,并得到按照字符排序的最大字符串

例如:
S = “aabcb”,返回结果为“acb” (分别删除了第一个a和b)

    public static String removeDuplicateLetters(String s) {
        HashMap<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            map.put(ch, map.getOrDefault(ch, 0) + 1);
        }
        Stack<Character> st = new Stack<>();
        // 记录stack里面有没有该字符
        HashMap<Character, Boolean> existHashMap = new HashMap<>();

        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (!existHashMap.containsKey(ch) || !existHashMap.get(ch)) {
                // map记录 还剩下多少个该字符串
                // 字符串后面还有stack顶的字符,并且比stack顶的字符大,才能把栈顶的字符pop出来,
                while (st.size() > 0 && map.containsKey(st.peek()) && st.peek()  < ch ) {
                    existHashMap.put( st.pop(), false);
                }
                st.push(ch);
                existHashMap.put(ch, true);
            }
            map.put(ch, map.get(ch) - 1);
            if (map.get(ch) == 0) {
                map.remove(ch);
            }
        }
        StringBuilder ans = new StringBuilder();
        while (st.size() > 0) {
            ans.insert(0, st.pop());
        }
        return ans.toString();
    }
上一篇下一篇

猜你喜欢

热点阅读