2
\$\begingroup\$

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?

\$\endgroup\$
1
\$\begingroup\$

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).

\$\endgroup\$
  • \$\begingroup\$ When the alphabet is big when compared to the strings, then it's slower. \$\endgroup\$ – maaartinus Jan 3 '17 at 17:15
  • \$\begingroup\$ @maaartinus including only letters from a to z.  the alphabet ia just 26 letters while we have no bound on string length. \$\endgroup\$ – Caridorc Jan 3 '17 at 21:36
  • \$\begingroup\$ What does alphabet represent in your snippet? Is it a Stream<String> of the alphabet? Wouldn't that solution iterate over each of s1 and s2 25 times in the worst case (think about two Strings, each containing the letter a 1000 times)? That would still give you a running time of O(n), but iterating over each String once is better than iterating 25 times. Using a HashSet as you later suggested would require a single iteration of the input strings (to build the HashSet), which is indeed more reasonable. \$\endgroup\$ – Eran Jan 4 '17 at 9:07
  • \$\begingroup\$ @Eran Yes, I think the type you suggested is most appropriate and yes, for long strings it is better to convert to HashSet once. \$\endgroup\$ – Caridorc Jan 4 '17 at 9:09
  • \$\begingroup\$ @Caridorc I just checked and it says my IDE cant resolve alphabet. I thought it was some predefined variable inside Java but I think I have to create it first, right? Same with variable letter? Here is the code: gist.github.com/doublemc/082b9fc6d0921d2348ef947e1709bf9f Your method is longest2. \$\endgroup\$ – ohwelppp Jan 4 '17 at 11:14
2
\$\begingroup\$

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();
}
\$\endgroup\$
  • \$\begingroup\$ Can you help me on this code review question of mine. I haven't got any answer so thought to check with you. \$\endgroup\$ – user5447339 Jan 4 '17 at 4:32
0
\$\begingroup\$

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();
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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