Java 8 Streams Remove Duplicate Letter

Question

I'm trying to apply my knowledge of streams to some leetcode algorithm questions. Here is a general summary of the question:

Given a string which contains only lowercase letters, remove duplicate letters so that every letter appears once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.

Example:

Input: "bcabc"
Output: "abc"

Another example:

Input: "cbacdcbc"
Output: "acdb"

This seemed like a simple problem, just stream the values into a new list from the string, sort the values, find the distinct values, and then throw it back into a list, and append the list's value to a string. Here is what I came up with:

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

The first example is working perfectly, but instead of "acdb" for the second output, I'm getting "abcd". Why would abcd not be the least lexicographical order? Thanks!

Allocate

yeah i'm aware of that, i was kind of looking to see if I can get it with streams based practice – Allocate

what exactly is the question? the order isn't correct or that the expected output is not what you think it should be? what is it from streams that you are looking for? – Outgoings

What is the order in 2nd example output? – Deaconry

Answer 1

As I had pointed out in the comments using a LinkedHashSet would be best here, but for the Streams practice you could do this:

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

Note: distinct() comes after sorted() in order to optimize the stream, see Holger's explanation in the comments as well as this answer.

Lot of different things here so I'll number them:

1. You can stream the characters of a String using String#chars() instead of making a List where you add all the characters.

2. To ensure that the resulting string is smallest in lexographical order, we can sort the IntStream.

3. We can convert the IntStream back to a String by performing a mutable reduction with a StringBuilder. We then convert this StringBuilder to our desired string.

A mutable reduction is the Stream way of doing the equivalent of something like:

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

However, this has the added benefit of using a StringBuilder for concatenation instead of a String. See this answer as to why this is more performant.

For the actual question you have about the conflict of expected vs. observed output: I believe abcd is the right answer for the second output, since it is the smallest in lexographical order.

Armagh

With the current version of the reference implementation, .sorted().distinct() is more efficient than .distinct().sorted(), because the subsequent distinct op will utilize the sorted nature of the data. – Crenulate

Answer 2

public static void main(String[] args) {
    String string = "cbacdcbc";
    string.chars()
            .mapToObj(item -> (char) item)
            .collect(Collectors.toSet()).forEach(System.out::print);

}

the output：abcd，hope help you!

Secondly

Answer 3

//1st Approach

String input = "aabscs";
Arrays.stream(input.split(""))
      .collect(Collectors.toSet()).forEach(System.out::print);

//2nd Approach

input.chars()
            .mapToObj(item -> (char) item)
            .collect(Collectors.toSet()).forEach(System.out::print);

//Output: absc

/** It can be done in multiple ways, we can also use Map, but I think this is a simple one.

Hope it will help you */

Hot

Answer 4

List<String> c = Arrays
  .asList("helloword".split(""))
  .stream()
  .distinct()
  .toList();

Thule

Your answer could be improved with additional supporting information. Please edit to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers in the help center. – Prom