删除重复项后选择字典最小字符串 [英] Select lexicographical smallest string after duplicates removed

问题描述

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

Remove all duplicates from a string and select the lexicographical smallest string possible. For example, the string cbacdcbc would return acdb, not adcb.

因此，如果我们不必选择字典编码最小的字符串，考虑到这个事实，我不知道如何来到一个有效的解决方案。这是我到目前为止：

So this has a relatively simple solution if we don't have to select the string that's lexicographical smallest, but considering that fact, I'm not sure how to come to an efficient solution. Here's what I have so far:

    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;
    }

推荐答案

strong>

Algorithm

1. 检查输入字符串中是否存在字母： a，b，c，d 。


2. 找到所有 b，c，d 的第一个 a
   
   或者如果不可能，找到第一个 b ，其中包含 a，c，d 。

或者如果不可能，找到第一个 c ，其中包含 a， b，d 。

或者如果不可能，找到第一个 d 。


3. 丢弃输入字符串的开头，直到所选字符。


4. 从第2步开始，找到剩余的字符。

1. Check which letters are present in the input string: a,b,c,d.
2. Find the first a that has all of b,c,d after it.
   Or if that's not possible, find the first b that has all of a,c,d after it.
   Or if that's not possible, find the first c that has all of a,b,d after it.
   Or if that's not possible, find the first d.
3. Discard the start of the input string up to the selected character.
4. Repeat from step 2 with the remaining characters to be found.

代码示例

;我的C ++是生锈的）。它创建一个位模式 chars 来存储仍然要找到的字符，以及一个数组之后的位模式存储每个位置后仍然可用的字符。

(in Javascript; my C++ is rusty). It creates a bit pattern chars to store which characters are still to be found, and an array after of bit patterns to store which characters are still available after each position.

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"));

这篇关于删除重复项后选择字典最小字符串的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！