美文网首页LeetCode
删除重复字符并且得到最大字符串

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

作者: Billsion | 来源:发表于2022-02-18 00:31 被阅读0次

    描述:
    给定一个字符串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();
        }
    

    相关文章

      网友评论

        本文标题:删除重复字符并且得到最大字符串

        本文链接:https://www.haomeiwen.com/subject/vbjrlrtx.html