Comparing two strings to see if string 2 is inside string 1

Here is what I have to do:


Write a function scramble(str1,str2) that returns true if a portion of str1 characters can be rearranged to match str2, otherwise returns false.


For example:

• str1 is 'rkqodlw' and str2 is 'world' the output should return true.

• str1 is 'cedewaraaossoqqyt' and str2 is 'codewars' should return true.

• str1 is 'katas' and str2 is 'steak' should return false.

Only lower case letters will be used (a-z). No punctuation or digits will be included.
Performance needs to be considered

public class Scramblies {
    public static boolean scramble(String str1, String str2) {
        String temp = str1;
        int count = 0;
        boolean result = true;
        for(int i=0 ; i<str2.length() ; i++){
            char c = str2.charAt(i);
            if(temp.contains(String.valueOf(c))){
                temp = temp.replaceFirst(String.valueOf(c), "");
                count++;
            }
        }
        if (count == str2.length()){
            result = true;
        } else {
            result = false;
        }
        return result;
    }
 }

My code works perfectly, but the only problem now is efficiency. I am tested against how long it takes to finish the final test class, which times out. I get this:


Process was terminated. It took longer than 10000ms to complete

How can this code be made more efficient to achieve the same result?

The problem with your approach is that you're traversing the second String as many times as there are elements in the first String with the replaceFirst call (which also involves a regular expression).

Also, this has nothing to do with performance, but you could just use

return count == str2.length();

instead of the long, and so more difficult to read,

boolean result = true;
if (count == str2.length()){
    result = true;
} else {
    result = false;
}
return result;

You can tackle this problem a lot more effectively by taking advantage of the fact that only lower case letters will be used (a-z). Consider the following approach:

• We know that there are 26 lower case characters. Let us create an array of 26 values int[] array = new int[26];.

• For each character c of the second String, we increment the value stored in the array at the position c - 'a': this corresponds to the alphabetical position of the character (based from 0: 'a' -> 0, 'b' -> 1, ..., 'z' -> 25).

• Then for each character c of the first String, we decrement the value stored at the alphabetical position.

• Finally, if at the end of this process, we end up with at least one value that is strictly positive, we know that the second String wasn't contained in the first one. This is because it means that we encountered a character in str2 more times than it was in str1 (it was incremented more times than it was decremented).

A sample implementation of this approach would be:

public static boolean scramble(String str1, String str2) {
    int[] array = new int[26];
    for (char c : str2.toCharArray()) {
        array[c - 'a']++;
    }
    for (char c : str1.toCharArray()) {
        array[c - 'a']--;
    }
    for (int value : array) {
        if (value > 0) {
            return false;
        }
    }
    return true;
}

You can test it with

public static void main(String[] args) {
    System.out.println(scramble("rkqodlw", "world")); // prints "true"
    System.out.println(scramble("cedewaraaossoqqyt", "codewars")); // prints "true"
    System.out.println(scramble("katas", "steak")); // prints "false"
}

StackExchange Code Review Q#124172, answer score: 18