如何在保留最小字典顺序的同时删除重复字母

Question

我有一项任务是从给定的字符串中删除重复项（经典面试问题），但这有点不同，最终结果应该是尽可能最小的字典顺序。例如，cbacdcbc => acdb, bcabc => abc。我在SO中看到了几个相关的问题，但我找不到答案。

编辑：这是我到目前为止的代码（无法正常工作）：

public static String removeDuplicateCharsAlphbetically(String str) {
    int len = str.length();
    if (len<2) return str;

    char[] letters = str.toCharArray();
    int[] counts = new int[26];
    for (char c : letters) {
        counts[c-97]++;
    }

    StringBuilder sb = new StringBuilder();

    for (int i=0;i<len-1;i++) {
        if (letters[i]==letters[i+1]) continue;

        if (counts[letters[i]-97]==1) {
            sb.append(letters[i]);
        } else if (counts[letters[i]-97] != 0) {
            if (letters[i]<letters[i+1] && counts[letters[i]-97] == 1) {
                sb.append(letters[i]);
                counts[letters[i]-97]=0;
            } else {
                counts[letters[i]-97]--;
            } 
        }

    }

    return sb.toString();
 }

EDIT2：我很抱歉没有提前提供问题的链接。这是链接：

Answer 1

这可以在 O(StringLenght) 时间内完成。字符串长度 = N; 时间复杂度 O(N) ，字符串的单次扫描。空间复杂度 O(26)

解决方案：

1. 创建一个 Alphabet 字母数组，用于存储指向双向链表 Node 的指针。

ListNode* array[26]; // Initialized with NULL value.

2. 创建一个空的链表，它将以相反的顺序表示任何时间点的解决方案字符串。

3. 扫描字符串，对于每个字母，检查字母，ltr，检查array[ltr-'a'] .... a.) 如果它是 NULL，则表示它是第一次出现并将其添加到链表中。... b.) 如果 array 指向任何节点 listNodeltr ，则表示 letter 已经在结果 i 中。检查前一个 listNode 到 listNodeltr 的值，在链接列表中，

如果值为listNodeltr->prev->val < listNode->val，则表示从该位置移除当前节点将使结果按字典顺序变小。所以从linkedList中的当前位置移除listNodeLtr并将其添加到最后。

Else, current postion of ltr is find and continue.

cba cdcbc

[a]->[b]->[c]

cbac dcbc [c]->[a]->[b]

cbacdc bc [d]->[c]->[a]->[b]

cbacdcb c [b]->[d]->[c]->[a]

cbacdcbc [b]->[d]->[c]->[a]

以相反的顺序打印链接列表：acdb。