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

Question

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

编辑：这是我到目前为止的代码（不正常）：

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：我不把问题：前面的链接遗憾。这里是link：

Answer 1

首先，我们来创建一组字符串s的所有不同的字母。这个集合的大小是答案的长度和算法中的步数。 我们将增加一个字母与下面的贪婪方法每一步的答案：

在每一步都按照字母顺序其余字母迭代，并为每一个字母l：

1. 找到的第一次出现l in s。我们将其命名为lpos。
2. 如果子串s[lpos, end]包含所有剩余的字母，然后将l添加到结果中，请将s替换为s[lpos+1, end]，然后转到下一步，设置缩小的剩余字母。

执行一些优化，以达到更好的时间复杂度：

public String removeDuplicateLetters(String s) { 
    StringBuilder result = new StringBuilder(); 
    int[] subsets = new int[s.length()]; 

    int subset = 0; 
    for (int i = s.length() - 1; i >= 0; i--) { 
     char ch = s.charAt(i); 
     subset = addToSet(subset, ch); 
     subsets[i] = subset; 
    } 

    int curPos = 0; 
    while (subset != 0) { 
     for (char ch = 'a'; ch <= 'z'; ++ch) { 
      if (inSet(subset, ch)) { 
       int chPos = s.indexOf(ch, curPos); 
       if (includes(subsets[chPos], subset)) { 
        result.append(ch); 
        subset = removeFromSet(subset, ch); 
        curPos = chPos + 1; 
        break; 
       } 
      } 
     } 
    } 

    return result.toString(); 
} 

private boolean inSet(int set, char ch) { 
    return (set & (1 << (ch - 'a'))) != 0;  
} 

private boolean includes(int set, int subset) { 
    return (set | subset) == set; 
} 

private int addToSet(int set, char ch) { 
    return set | (1 << (ch - 'a')); 
} 

private int removeFromSet(int set, char ch) { 
    return set & ~(1 << (ch - 'a')); 
} 

可运行版本：https://ideone.com/wIKi3x

Answer 2

观察1：输出的第一个字母是最小的字母，所有其他字母出现在字符串中最左边的外观的右侧。

观察2：输出的其余字母是第一个字母最左侧外观右侧字母的子序列。

这提示了递归算法。

def rem_dups_lex_least(s): 
    if not s: 
     return '' 
    n = len(set(s)) # number of distinct letters in s 
    seen = set()  # number of distinct letters seen while scanning right to left 
    for j in range(len(s) - 1, -1, -1): # len(s)-1 down to 0 
     seen.add(s[j]) 
     if len(seen) == n: # all letters seen 
      first = min(s[:j+1]) 
      i = s.index(first) # leftmost appearance 
      return first + rem_dups_lex_least(''.join(c for c in s[i+1:] if c != first)) 

Answer 3

从输入端向后将开始建设的结果。在每一步：

1. 如果遇到新字母，请在其前面加上结果。
2. 如果遇到重复，则将其与结果的头部进行比较。如果head更大，请从结果中删除重复项，并将其前置。

LinkedHashSet对存储结果集及其内部顺序都是很好的。

public static String unduplicate(String input) { 
    Character head = null; 
    Set<Character> set = new LinkedHashSet<>(); 
    for (int i = input.length() - 1; i >= 0; --i) { 
     Character c = input.charAt(i); 
     if (set.add(c)) 
      head = c; 
     else if (c.compareTo(head) < 0) { 
      set.remove(c); 
      set.add(head = c); 
     } 
    } 
    StringBuilder result = new StringBuilder(set.size()); 
    for (Character c: set) 
     result.append(c); 
    return result.reverse().toString(); 
}