去除重复字母

# -*- 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

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("")
}