去除重复字母

# -*- coding: utf-8 -*-

import collections

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param str string字符串
# @return string字符串
#
class Solution:
    """
    题目：
        https://www.nowcoder.com/practice/67bf02ee92304e1f822d12742cec0725?tpId=196&tqId=40506&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3Fpage%3D8%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=undefined&tags=&title=
    参考：
        https://leetcode.cn/problems/remove-duplicate-letters/solution/qu-chu-zhong-fu-zi-mu-by-leetcode-soluti-vuso/
    算法：
        题目要求对字符串中的重复字符去重，仅保留一次，最终使得整个字符串的字典序最小。
        如何保证字典序最小，对于逆序对str[i] > str[i+1]，我们应该删除字符str[i]。
        我们从前向后扫描原字符串。每扫描到一个位置，我们就尽可能地处理所有的逆序对。假定在扫描位置 s[i-1] 之前的所有逆序对都已经被去除完毕，在扫描字符 s[i] 时，新出现的「关键字符」只可能出现在 s[i] 或者其后面的位置。
        遍历字符串str：
            如果当前字符ch = str[i]未出现过：
                处理逆序对，更新hashSet与单调栈stack。
            否则：
                忽略该字符
            处理完毕，当前字符出现次数-1
        需要注意的是：
            对于字符str[i]，如果已存在于stack中，则不能再入栈。所以我们使用hashSet记录单调栈内元素。
            对于重复字符，要保留一次。这里我们统计每个字符的剩余次数，如果剩余次数为0，则不能删除。
    复杂度：
        时间复杂度：O(N)
        空间复杂度：O(N)
    """

    def removeDuplicateLetters(self, str):
        # write code here
        n = len(str)
        hashSet, stack = set(), []
        count = collections.Counter(str)

        for i in range(n):
            ch = str[i]
            if ch not in hashSet:
                while stack and stack[-1] >= ch and count[stack[-1]] > 0:
                    hashSet.remove(stack[-1])
                    stack.pop()
                stack.append(ch)
                hashSet.add(ch)
            count[ch] -= 1

        return "".join(stack)


if __name__ == "__main__":
    sol = Solution()

    # str = "abcd"

    # str = "acbcd"

    # str = "bjffaigbafeh"

    str = "egdhdjjahadja"

    res = sol.removeDuplicateLetters(str)

    print res

import java.util.*;

/**
 * NC375 去除重复字母
 * @author d3y1
 */
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param str string字符串
     * @return string字符串
     */
    public String removeDuplicateLetters (String str) {
        // return solution1(str);
        // return solution2(str);
        return solution3(str);
    }

    /**
     * 贪心+单调栈
     * @param str
     * @return
     */
    private String solution2(String str){
        int n = str.length();

        HashMap<Character, Integer> lastIndexMap = new HashMap<>();
        char cur;
        for(int i=n-1; i>=0; i--){
            cur = str.charAt(i);
            if(!lastIndexMap.containsKey(cur)){
                lastIndexMap.put(cur, i);
            }
        }

        Deque<Integer> deque = new LinkedList<>();
        HashSet<Character> usedSet = new HashSet<>();
        // 贪心
        for(int i=0; i<n; i++){
            cur = str.charAt(i);
            // 测试用例: ambcadcb -> ambcd
            // 测试用例: mabcadcb -> mabcd
            if(usedSet.contains(cur)){
                continue;
            }
            // 单调栈(单调增)
            // lastIndexMap.get(str.charAt(deque.peekLast()))>i -> 表示栈顶字符在右侧(后面)有重复
            while(!deque.isEmpty() && str.charAt(deque.peekLast())>cur && lastIndexMap.get(str.charAt(deque.peekLast()))>i){
                usedSet.remove(str.charAt(deque.pollLast()));
            }
            deque.offerLast(i);
            usedSet.add(cur);
        }

        StringBuilder result = new StringBuilder();
        while(!deque.isEmpty()){
            result.append(str.charAt(deque.pollFirst()));
        }

        return result.toString();
    }

    /**
     * 贪心+单调栈
     * @param str
     * @return
     */
    private String solution3(String str){
        int n = str.length();
        char[] letters = str.toCharArray();
        int[] lastIndex = new int[26];

        // 当前字符 最后索引位置
        for(int i=0; i<n; i++){
            lastIndex[letters[i]-'a'] = i;
        }

        boolean[] isUsed = new boolean[26];
        Deque<Character> deque = new ArrayDeque<>();
        char cur;
        // 贪心
        for(int i=0; i<n; i++){
            cur = letters[i];
            if(isUsed[cur-'a']){
                continue;
            }
            // 单调栈(单调增)
            // lastIndex[deque.peekLast()-'a']>i -> 表示栈顶字符在右侧(后面)有重复
            while(!deque.isEmpty() && deque.peekLast()>cur && lastIndex[deque.peekLast()-'a']>i){
                isUsed[deque.pollLast()-'a'] = false;
            }
            deque.offerLast(cur);
            isUsed[cur-'a'] = true;
        }

        StringBuilder result = new StringBuilder();
        while(!deque.isEmpty()){
            result.append(deque.pollFirst());
        }

        return result.toString();
    }

    //////////////////////////////////////////////////////////////////////////////////////

    /**
     * 贪心+单调栈
     * @param str
     * @return
     */
    private String solution1(String str){
        Stack<Character> stack = new Stack<>();
        boolean[] isVisited = new boolean[26];
        int[] lastIndex = new int[26];
        char[] chars = str.toCharArray();
        int len = chars.length;

        for(int i=0; i<len; i++){
            lastIndex[chars[i]-'a'] = i;
        }

        // 贪心 瞻前顾后
        for(int i=0; i<len; i++){
            // 瞻前
            if(isVisited[chars[i]-'a']){
                continue;
            }
            // 单调栈(单调增)
            // lastIndex[stack.peek()-'a']>i -> 表示栈顶字符在右侧(后面)有重复 (顾后)
            while(!stack.isEmpty() && stack.peek()>chars[i] && lastIndex[stack.peek()-'a']>i){
                isVisited[stack.pop()-'a'] = false;
            }
            stack.push(chars[i]);
            isVisited[chars[i]-'a'] = true;
        }

        StringBuilder sb = new StringBuilder();
        while(!stack.isEmpty()){
            sb.append(stack.pop());
        }

        return sb.reverse().toString();
    }
}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param str string字符串
     * @return string字符串
     */
    public String removeDuplicateLetters (String str) {
        // write code here
        int [] cnt = new int [26];
        for (int i = 0; i < str.length(); i++) {
            cnt[str.charAt(i) - 'a']++;
        }
        int pos = 0;
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(pos) > str.charAt(i)) {
                pos = i;
            }
            if (--cnt[str.charAt(i) - 'a'] == 0) {
                break;
            }
        }
        return str.length() == 0 ? "" : str.charAt(pos) + 
            removeDuplicateLetters(str.substring(pos + 1).replaceAll("" + str.charAt(pos), ""));
    }
}

function removeDuplicateLetters( str ) {
    // write code here
    let stack=[]
    for(let i=0;i<str.length;i++){
        if(stack.includes(str[i]))continue
        while(stack[stack.length-1]>str[i]&&str.indexOf(stack[stack.length-1],i)>-1){
            stack.pop()
        }
        stack.push(str[i])
    }
    return stack.join("")
}