Java 8 Streams 删除重复字母

Question

我正在尝试将我的流知识应用于一些 leetcode 算法问题。以下是问题的一般摘要：

给定一个只包含小写字母的字符串，删除重复的字母，使每个字母只出现一次。您必须确保您的结果在所有可能的结果中按字典顺序最小。

例子：

Input: "bcabc"
Output: "abc"

另一个例子：

Input: "cbacdcbc"
Output: "acdb"

这似乎是一个简单的问题，只需将值从字符串流式传输到新列表中，对值进行排序，找到不同的值，然后将其扔回列表中，并将列表的值附加到字符串中。这是我想出的：

public String removeDuplicateLetters(String s)
{
    char[] c = s.toCharArray();
    List<Character> list = new ArrayList<>();
    for(char ch : c) 
    {
        list.add(ch);
    }
    
    List<Character> newVal = list.stream().distinct().collect(Collectors.toList()); 
    String newStr = "";
    for(char ch : newVal) 
    {
        newStr += ch;
    }
    
    return newStr;
}

第一个示例运行良好，但第二个输出不是“acdb”，而是“abcd”。为什么 abcd 不是最小的字典顺序？谢谢！

Answer 1

正如我在评论中指出的，LinkedHashSet在这里使用 a 是最好的，但对于Streams 实践，你可以这样做：

public static String removeDuplicateLetters(String s) {
    return s.chars().sorted().distinct().collect(
        StringBuilder::new,
        StringBuilder::appendCodePoint,
        StringBuilder::append
    ).toString();
}

注意：distinct()为了sorted()优化流，请参阅 Holger 在评论中的解释以及此答案。

这里有很多不同的东西，所以我将它们编号：

1. String您可以使用流式传输 a 的字符，String#chars()而不是在其中List添加所有字符。

2. 为了确保结果字符串按字典顺序最小，我们可以对IntStream.

3. 我们可以通过使用a执行可变归约IntStream来将back 转换为 a 。然后我们将其转换为我们想要的字符串。StringStringBuilderStringBuilder

可变归约相当于Stream执行以下操作：

for (char ch : newVal) {
    newStr += ch;
}

然而，这还有一个额外的好处，那就是使用StringBuilderfor 连接而不是String. 请参阅此答案以了解为什么它的性能更高。

对于您关于预期输出与观察到输出的冲突的实际问题：我相信这abcd是第二个输出的正确答案，因为它是按字典顺序排列的最小输出。