SOURCE

// 给定一个字符串，请去掉其中的重复字符，使得最终的字符串不含重复字符。

// 比如

// 'xyzabcxyzabc'
// 每个字符都出现了两次，可以去掉其中的一半，得到如下字符串。

// 'xyzabc'
// 'xyabcz'
// 'xabcyz'
// 'abcxyz'
// 'abxyzc'
// .....
// 以上字符串都不含重复字符，但是你需要返回字典序中最小的，也就是'abcxyz'。

// 所有的参数都只会是有效的小写字母。


function mallestUniqueSubstr(str) {
    const lastIndex = new Map();

    for (let i = 0; i < str.length; i++) {
        lastIndex.set(str[i], i);
    };

    const stack = [];
    const inStack = new Set();

    for (let i = 0; i < str.length; i++) {
        const char = str[i];

        if (inStack.has(char)) continue;

        while (stack.length && stack[stack.length - 1] > char && lastIndex.get(stack[stack.length - 1]) > i) {
            const top = stack.pop();
            inStack.delete(top);
        };

        stack.push(char);
        inStack.add(char);
    };

    return stack.join('');
};



// 测试
console.log(mallestUniqueSubstr('xyzabcxyzabc')); // 'abcxyz'