c++ - 删除重复后选择字典序最小的字符串

Question

从字符串中删除所有重复项并尽可能选择字典序最小的字符串。例如，字符串 cbacdcbc 将返回 acdb，而不是 adcb。

因此，如果我们不必选择字典序最小的字符串，那么这是一个相对简单的解决方案，但考虑到这一事实，我不确定如何得出有效的解决方案。这是我到目前为止所拥有的:

    string removeDuplicateLetters(string s)
    {
        vector<bool> v(26,0);
        for(int i = 0; i < s.size(); i++) {
            v[s[i]-'a'] = 1;
        }

        string ss = "";
        for(int i = 0; i < s.size(); i++) {
            if(v[s[i]-'a']) {
                ss += s[i];
                v[s[i]-'a'] = 0;
            }
        }

        return ss;
    }

Answer 1

算法

1. 检查输入字符串中出现了哪些字母:a,b,c,d。
2. 找到第一个a，它后面有所有的b,c,d。
   或者，如果这不可能，请找到第一个 b，它后面有所有 a,c,d。
   或者，如果这不可能，请找到第一个 c，它后面有所有 a,b,d。
   或者，如果这不可能，请找到第一个 d。
3. 丢弃输入字符串的开头到所选字符。
4. 从步骤 2 开始重复，找到剩余的字符。

代码示例

(在 Javascript 中；我的 C++ 生锈了)。它创建一个位模式 chars 来存储哪些字符仍然有待找到，并创建一个位模式数组 after 来存储在每个位置之后哪些字符仍然可用。

function smallestString(input) {
    var chars = 0, after = [];
    for (var i = input.length - 1; i >= 0; i--) {
        chars |= 1 << (input.charCodeAt(i) - 97);
        after[i] = chars;
    }
    var result = "", start = 0, pos;
    while (chars) {
        for (var i = 0; i < 26; i++) {
            if (chars & (1 << i)) {
                pos = input.indexOf(String.fromCharCode(97 + i), start);
                if (chars == (chars & after[pos])) {
                    result += String.fromCharCode(97 + i);
                    chars -= 1 << i;
                    break;
                }
            }
        }
        start = pos + 1;
    }
    return result;
}

document.write(smallestString("cbacdcbc") + "<BR>");
document.write(smallestString("thequickbrownfoxjumpsoverthelazydog"));