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

Question

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?

Answer 1

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"
}

Answer 2

This is comparatively easy when we use Java streams with anyMatch. Let's look at this program.

public class Test2 {
    public static void main(String[] args) {

        String a = "Gina Gini Protijayi Soudipta";
        String b = "Gini";

        System.out.println(WordPresentOrNot(a, b));
    }// main

    private static boolean WordPresentOrNot(String a, String b) {
    //contains is case sensitive. That's why,change it to upper or lower case. Then check
        // Here we are using stream with anyMatch
        boolean match = Arrays.stream(a.toLowerCase().split(" ")).anyMatch(b.toLowerCase()::contains);
        return match;
    }

}

Answer 3

Another method would be to sort all the letters in both strings. If the first value in string 1 doesn't match the first value in string 2, skip it. If the first value in both string 1 and string 2 match, skip both. If you run out of string 1 while there are still values in string 2 there is no match. If you consume all of string2's values, you match.