2
\$\begingroup\$

I am trying to return distinct characters from the combination of 2 Strings. The following is my solution which seems to work based on my tests.

Is there a more efficient way of going about this? I have converted the strings to arrays, to sets, to a StringBuilder and back to a String. I'm wondering if I have overcomplicated something which could have been resolved a lot simpler.

public String longest (String s1, String s2) {

    String[] s1Arr = s1.split("");
    String[] s2Arr = s2.split("");

    Set<String> arr1 = new HashSet<>(Arrays.asList(s1Arr));
    Set<String> arr2 = new HashSet<>(Arrays.asList(s2Arr));

    arr1.addAll(arr2);

    StringBuilder sb = new StringBuilder();
    Iterator<String> it = arr1.iterator();
    while (it.hasNext()){
        String element = it.next();
        sb.append(element);
    }

    return sb.toString();
}
\$\endgroup\$
2
  • \$\begingroup\$ It's a bit odd that you return the result as a String, when the order of entries is arbitrary. What is the use case for this code? \$\endgroup\$ Commented Nov 20, 2016 at 15:40
  • \$\begingroup\$ arr2 is not needed since you can directly add the second list to the first set: arr1.addAll(Arrays.asList(s2Arr)); also I agree with @200_success: the output is most likely more useful if you order the result before converting it back to a string. \$\endgroup\$ Commented Nov 20, 2016 at 16:45

3 Answers 3

3
\$\begingroup\$

What comes to performance, you can improve it significantly:

public static String getDistinctCharString(String s1, String s2) {
    Set<Character> set = new HashSet<>(s1.length() + s2.length());

    char[] chars1 = s1.toCharArray();
    char[] chars2 = s2.toCharArray();

    for (char c : chars1) {
        set.add(c);
    }

    for (char c : chars2) {
        set.add(c);
    }

    StringBuilder sb = new StringBuilder(set.size());

    for (char c : set) {
        sb.append(c);
    }

    return sb.toString();
}

The point is that you deal with characters rather than substrings of length 1.

My demonstration gives me the following output:

longest() in 2558 ms.
getDistinctCharString() in 342 ms.
Algorithms agree: true

Hope that helps.

\$\endgroup\$
1
  • \$\begingroup\$ if you are setting HashSet size, you should do it right. \$\endgroup\$
    – devops
    Commented Nov 21, 2016 at 18:22
2
\$\begingroup\$

With Java8, this problem can be solved somewhat easily:

public static String java8Version(
        final String s1,
        final String s2) {
    ////
    return IntStream.concat(s1.chars(), s2.chars()).distinct()
            .collect(StringBuilder::new, StringBuilder::appendCodePoint, StringBuilder::append)
            .toString();
}

Below approximated times, for shorter input-strings coderodde's solution has the upper hand, for larger strings the IntStream version seems to be preferable:

Benchmark for two strings of length n, seeds for randoms: 14536426262341L and 536475869798457L (number of distinct characters are 1968, 17254, 62399 and 65536):
(Ievgen Anikushyn's version is without the sorted() call, other versions are 1:1 copied)

Benchmark                  (n)  Mode  Cnt        Score        Error  Units
getDistinctCharString     1000  avgt   25      142.482 ±      4.349  us/op
getDistinctCharString    10000  avgt   25     1184.946 ±     43.352  us/op
getDistinctCharString   100000  avgt   25    17690.026 ±   1511.287  us/op
getDistinctCharString  1000000  avgt   25   223346.656 ±   8074.609  us/op
java8Version              1000  avgt   25      151.340 ±      4.785  us/op
java8Version             10000  avgt   25     1485.053 ±     43.114  us/op
java8Version            100000  avgt   25    13637.576 ±    488.871  us/op
java8Version           1000000  avgt   25   159596.194 ±   4782.828  us/op
java8IevgenAnikushyn      1000  avgt   25      231.984 ±      5.321  us/op
java8IevgenAnikushyn     10000  avgt   25     2280.803 ±     99.742  us/op
java8IevgenAnikushyn    100000  avgt   25    31600.095 ±    851.614  us/op
java8IevgenAnikushyn   1000000  avgt   25   341541.386 ±   7357.557  us/op
longest                   1000  avgt   25      306.865 ±      9.798  us/op
longest                  10000  avgt   25     3510.012 ±    116.975  us/op
longest                 100000  avgt   25    65478.694 ±   1832.871  us/op
longest                1000000  avgt   25  1854812.781 ± 473216.482  us/op
\$\endgroup\$
1
\$\begingroup\$

Java 8. For any number of strings:

public static String getDistinctCharString(String... strings) {
        return Stream.of(strings)
                .map(String::chars)
                .flatMap(intStream -> intStream.mapToObj(charCode -> new String(new char[]{(char) charCode})))
                .distinct()
                .sorted()
                .collect(joining());
    }

Elapsed time: 141 ms

Sorted is optional. Or a bit refactored version:

public static String getDistinctCharString(String... strings) {
        return Stream.of(strings)
                .map(String::chars)
                .flatMap(intStream -> intStream.mapToObj(charCode -> (char) charCode))
                .distinct()
                .sorted()
                .map(character -> new String(new char[]{character}))
                .collect(joining());
    }
Elapsed time: 137 ms
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.