0

从字符串中删除所有重复项并选择可能的字典最小字符串。例如，字符串 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;
    }
4

4 回答 4

3

算法

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

于 2015-12-27T02:49:58.123 回答
1

m69 的 c++ 中的 javascript：

string smallestString(string input) {
    int chars = 0;
    int after[sizeof(input)];
    for (int i = input.length() - 1; i >= 0; i--) {
        chars |= 1 << (input[i] - 97);
        after[i] = chars;
    }
    string result = "";
    int start = 0, pos;
    while (chars) {
        for (int i = 0; i < 26; i++) {
            if (chars & (1 << i)) {
                pos = input.find('a' + i, start);
                if (chars == (chars & after[pos])) {
                    result += 'a' + i;
                    chars -= 1 << i;
                    break;
                }
            }
        }
        start = pos + 1;
    }
    return result;
}
于 2015-12-27T04:33:28.570 回答
0

我觉得这种方法很简单。

首先找到每个字符的计数。

输入：s

vector<int> cnt(26);
int n=s.size();
for(int i=0;i<n;i++) cnt[s[i]-'a']++;

有一个访问过的向量，vector<bool> visit(26);

string ans="";
for(int i=0;i<n;i++){
    int t=s[i]-'a';
    cnt[t]--;
    if(visit[t]) continue;
    while(ans.size()>0 && s[i]<ans.back() && cnt[ans.back()-'a']>0){
        visit[ans.back()-'a']=false;
        ans.pop_back();
    }
    ans.push_back(s[i]);
    visit[t]=true;
}
return ans;

时间复杂度为 O(n)

于 2019-06-27T09:57:58.927 回答
0

算法草图。

  1. 传递字符串，构建每个字符出现次数的映射，以及每个字符最右边（也可能是唯一）出现的位置。

  2. 找到可以出现在第一个位置的最小字符。为此，请从左到右，注意遇到的最小字符；当您击中任何字符的最右侧出现时停止。删除最小字符之前的所有字符，以及最小字符的所有其他副本；相应地更新地图。

  3. 从第 2 步中最小字符之后的字符开始重复。

可以在映射中的所有计数器达到 1 时提前终止。删除其他副本可以与正常迭代相结合（只需在计数器映射中将要删除的字符标记为 0，在正常搜索中跳过它们，当去掉前缀）。

这个算法在最坏的情况下是二次的，至少在字母表的大小上是这样的（最坏的情况是abc...zabc...; 该算法检查每个字符的一半字符串，只是决定保留它）。我认为这可以通过在一种优先级队列结构中不仅跟踪最小的，而且跟踪第二小的和第三小的等等来解决（细节留给读者练习）。

于 2015-12-27T02:49:14.010 回答