Two strings to one containing distinct letters

Question

I've been doing lately CodeWars and here's my working code for this challenge.

The challenge :

Take 2 strings s1 and s2 including only letters from a to z. Return a new sorted string, the longest possible, containing distinct letters, - each taken only once - coming from s1 or s2.

My code :

public static String longest(String s1, String s2) {
    StringBuilder sb = new StringBuilder();
    sb.append(s1).append(s2);

    String s = sb.toString();
    String result = "";

    for (int i = 0; i < s.length(); i++) {
        if (!result.contains(String.valueOf(s.charAt(i)))) {
            result += s.charAt(i);
        }
    }
    char[] ch = result.toCharArray();
    Arrays.sort(ch);

    return String.valueOf(ch);

}

Is there a way to skip all the transformations to arrays and then back to a String? I found it quite useful to use Arrays.sort because I didnt have to do another loop to sort chars in a String (dont think there is a StringBuilder method to sort chars as String is immutable, right?) Saw other solutions and many of them use streams but I havent learned about them yet so not trying to use them. Also I think there is no point in assigning String s becasue I can use sb.length() if a for loop and avoid another variable, right?

Answer 1

You can just Iterate over the alphabet discarding all the letters not inside at least one string:

return alphabet.filter(letter -> s1.contains(letter) || s2.contains(letter))

Given that the alphabet is already sorted, We can skip the sorting step altogether.

Using Java8 methods We can focus more on the logic than the looping and accumulating.

This is faster and you can speed up this even more if you input the characters not as strings but as HashSets, this way running time becomes \$O(1)\$, that is constant with the size of the input (You need \$O(N)\$ at the start to create the HashSets though).

Answer 2

First of all, you can work directly with chars instead of creating one char Strings.

Second of all, looking at the challenge description

Take 2 strings s1 and s2 including only letters from ato z. Return a new sorted string, the longest possible, containing distinct letters, - each taken only once - coming from s1 or s2.

you disregard an important part - there is a small number of possible unique characters in the input Strings. You can use that information to your advantage and eliminate the need to explicitly sort the output String.

For example, you can use an int array of length 26 to indicate for each letter of the abc whether it is present in one of the input Strings.

You can populate the array by iterating once over each of the input Strings. Then you can iterate once over that array and add to the output String the characters corresponding with indices of the array for which the value > 0.

This would reduce your time complexity from O(nlogn) to O(n).

public static String longest(String s1, String s2) {
    int[] chars = new int[26];
    for (char c : s1.toCharArray()) {
        chars[c-'a']=1;
    }
    for (char c : s2.toCharArray()) {
        chars[c-'a']=1;
    }
    StringBuilder result = new StringBuilder(26);
    for (int i = 0; i < chars.length; i++) {
        if (chars[i] > 0)
            result.append ((char)(i+'a'));
    }    
    return result.toString();
}

Answer 3

This could be the fastest solution, though not the nicest.

// A java.util.BitSet would be a more general solution.
// This one is slightly faster.
int bitset = 0;
for (int i = 0; i < s1.length(); i++) {
   bitset |= 1 << (s1.charAt(i) - 'a');
}
for (int i = 0; i < s2.length(); i++) {
   bitset |= 1 << (s2.charAt(i) - 'a');
}

// Not, bitset has ones in all positions corresponding
// with letters present in an input string.

StringBuilder result = new StringBuilder();
for (char c = 'a'; c <= 'Z'; ++c) {
    if ((bitset & (1 << (c - 'a')) != 0) {
        result.append(c);
    }
}
return result.toString();