CODEWITHSUNDEEP
javaalgorithmjava-streamunique
PainIsAMaster
PainIsAMaster

Reputation: 2076

Getting intermediate results from stream to be used later in stream

I was trying to write some functional programming code (using lambdas and streams from Java 8) to test if a string has unique characters in it (if it does, return true, if it does not, return false). A common way to do this using vanilla Java is with a data structure like a set, i.e.:

public static boolean oldSchoolMethod(String str) {
    Set<String> set = new HashSet<>();

    for(int i=0; i<str.length(); i++) {
        if(!set.add(str.charAt(i) + "")) return false;
    }
    return true;
}

The set returns true if the character/object can be added to the set (because it did not exist there previously). It returns false if it cannot (it exists in the set already, duplicated value, and cannot be added). This makes it easy to break out the loop and detect if you have a duplicate, without needing to iterate through all length N characters of the string.

I know in Java 8 streams you cannot break out a stream. Is there anyway way to capture the return value of an intermediate stream operation, like adding to the set's return value (true or false) and send that value to the next stage of the pipeline (another intermediate operation or terminal stream operation)? i.e.

Arrays.stream(myInputString.split(""))
    .forEach( i -> {
       set.add(i) // need to capture whether this returns "true" or "false" and use that value later in 
                  // the pipeline or is this bad/not possible?
    });

One of the other ways I thought of solving this problem, is to just use distinct() and collect the results into a new string and if it is the same length as the original string, than you know it is unique, else if there are different lengths, some characters got filtered out for not being distinct, thus you know it is not unique when comparing lengths. The only issue I see here is that you have to iterate through all length N chars of the string, where the "old school" method best-case scenario could be done in almost constant time O(1), since it is breaking out the loop and returning as soon as it finds 1 duplicated character:

public static boolean java8StreamMethod(String str) {
    String result = Arrays.stream(str.split(""))
            .distinct()
            .collect(Collectors.joining());

    return result.length() == str.length();
}

Upvotes: 0

Views: 334

Answers (3)

Holger
Holger

Reputation: 298389

Your solutions are all performing unnecessary string operations.

E.g. instead of using a Set<String>, you can use a Set<Character>:

public static boolean betterOldSchoolMethod(String str) {
    Set<Character> set = new HashSet<>();
    for(int i=0; i<str.length(); i++) {
        if(!set.add(str.charAt(i))) return false;
    }
    return true;
}

But even the boxing from char to Character is avoidable.

public static boolean evenBetterOldSchoolMethod(String str) {
    BitSet set = new BitSet();
    for(int i=0; i<str.length(); i++) {
        if(set.get(str.charAt(i))) return false;
        set.set(str.charAt(i));
    }
    return true;
}

Likewise, for the Stream variant, you can use str.chars() instead of Arrays.stream(str.split("")). Further, you can use count() instead of collecting all elements to a string via collect(Collectors.joining()), just to call length() on it.

Fixing both issues yields the solution:

public static boolean newMethod(String str) {
    return str.chars().distinct().count() == str.length();
}

This is simple, but lacks short-circuiting. Further, the performance characteristics of distinct() are implementation-dependent. In OpenJDK, it uses an ordinary HashSet under the hood, rather than BitSet or such alike.

Upvotes: 4

Stefan Winkler
Stefan Winkler

Reputation: 3966

What about just mapping to a boolean?

Arrays.stream(myInputString.split(""))
   .map(set::add)
   .<...>

That would solve your concrete issue, I guess, but it's not a very nice solution because the closures in stream chains should not have side-effects (that is exactly the point of functional programming...).

Sometimes the classic for-loop is still the better choice for certain problems ;-)

Upvotes: 1

Joby Wilson Mathews
Joby Wilson Mathews

Reputation: 11126

This code might work for you:

public class Test {

    public static void main(String[] args) {

        String myInputString = "hellowrd";

        HashSet<String> set = new HashSet<>();
        Optional<String> duplicateChar =Arrays.stream(myInputString.split("")).
                filter(num-> !set.add(num)).findFirst();
        if(duplicateChar.isPresent()){
            System.out.println("Not unique");
        }else{
            System.out.println("Unique");
        }

    }
}

Here using findFirst() I am able to find the first duplicate element. So that we don't need to continue on iterating rest of the characters.

Upvotes: 3

Related Questions