Check if two strings are permutations of one another

Question

I am working my way through "Cracking the coding interview" problems and have finished implementing this question: "Given, two strings, write a method to decide if one is a permutation of the other". Can anyone give me any feedback on my implementation in regards of efficiency or improvements?

public static boolean containsPremutation(String firstString, String secondString){

    //Checking if either string is empty.
    if(firstString.isEmpty() || secondString.isEmpty())
        return false;

    //Checking if one string is larger than the other.
    if(firstString.length() > secondString.length() || secondString.length() > firstString.length())
        return false;

    //First convert the Strings into char[]
    char [] charFirstString =  firstString.toCharArray();
    char [] charSecondString = secondString.toCharArray();

    //Secondly, aplhabetize/sort the char arrays
    Arrays.sort(charFirstString);
    Arrays.sort(charSecondString);

    //Thirdly, create new Strings out of the sorted char arrays
    String alphaFirstString = new String(charFirstString);
    String alphaSecondString  = new String(charSecondString);

    //Now you can begin comparing each char in the Strings.
    // Begin iterating at the same char and if they are not the same char return false
    //otherwise continue iterating.
    for (int i = 0; i < alphaFirstString.length(); i++){
        if(alphaFirstString.charAt(i) != alphaSecondString.charAt(i))
            return false;
    }
    return true;

Answer 1

This question has used the word "permutation" for two strings, and in standard English what that's asking for is "is one the anagram of the other"? Using "anagram" as a search would help you find a lot of other information on this problem, especially on Code Review.

Your solution is significantly over-engineered. You have broken down the problem in to too many steps, and you've missed an opportunity to show how you would avoid code duplication.

Let's break down your code in to its stages:

1. Check each string is valid input
2. Check the strings are the same length
3. Extract the characters from each string
4. Sort each string's characters
5. Create a new String from each input's sorted characters.
6. Iterate over each of the sorted string's characters and compare to the other string.
7. Return the match status

Now, let's strip out the redundant parts... for example, you don't need to convert the sorted characters back to a string only to loop over each character again.... get rid of stage 5 and convert stage 6 to operate over the sorted array.

Also, stage 1, that's a bug. Two empty strings are anagrams of each other... agreed? Get rid of that check.

Now, what's left is two identical operations performed on two different inputs, which are then compared, so extract the common logic in to a function (Code reuse is a good thing):

private static final char[] sortedChars(String input) {
     char [] chars =  input.toCharArray();
     Arrays.sort(chars);
     return chars;
}

Then, your code looks like:

public static boolean containsPremutation(String firstString, String secondString){
    char[] firstChars = sortedChars(firstString);
    char[] secondChars = sortedChars(secondString);

    ....

}

Now what? Instead of converting them to strings, we can use the core library's Arrays class to do the comparisons for us:

return Arrays.equals(firstSorted, secondSorted);

The full code would be:

private static final char[] sortedChars(String input) {
     char [] chars =  input.toCharArray();
     Arrays.sort(chars);
     return chars;
}

public static boolean containsPremutation(String firstString, String secondString){
    char[] firstChars = sortedChars(firstString);
    char[] secondChars = sortedChars(secondString);

    return Arrays.equals(firstSorted, secondSorted);
}

Looking at the code that way, you can see other issues too...

• generally, "Hungarian Notation" is frowned on in Java Code Style - don't have String appended to variable names like firstString and secondString ... we know that they are strings.

• do we even need the variables in the contains... method? Could it just be:

  public static boolean containsPremutation(String first, String second){
      return Arrays.equals(sortedChars(first), sortedChars(second));
  }
  

• As mentioned in a comment, it's Permutation and not Premutation.

Answer 2

Even though rolfl already gave a great review, let me also mention some minor points:

• It's good practice to always put braces around blocks. This prevents simple bugs introduced by trying to amend the single-line block and forgetting the braces
• Checking for "different length" is easier with if (firstString.length() != secondString.length())
• You're overcommenting. A lot of these comments can be made or already are redundant through proper naming.
• Your placement of spaces is somewhat interesting:
  • In java usually the array indicators are placed directly adjacent to the type (char[] over char []).
  • An opening parenthesis for if, for, while and other block scopes is usually placed with one space distance. You're not consistent in how you do it. If statements don't get space, but for-loops do (if( vs for ()

Answer 3

    //Checking if either string is empty.
    if(firstString.isEmpty() || secondString.isEmpty())
        return false;

This doesn't seem right. Now if you have two empty strings, they are not permutations of each other. Why?

All other cases caught by this code would be caught by

    //Checking if one string is larger than the other.
    if(firstString.length() > secondString.length() || secondString.length() > firstString.length())
        return false;

Which might more briefly be written

    if (firstString.length() != secondString.length()) {
        return false;
    }

If one of the strings is empty and the other isn't, it will fail this check.

    //Thirdly, create new Strings out of the sorted char arrays
    String alphaFirstString = new String(charFirstString);
    String alphaSecondString  = new String(charSecondString);

    //Now you can begin comparing each char in the Strings.
    // Begin iterating at the same char and if they are not the same char return false
    //otherwise continue iterating.
    for (int i = 0; i < alphaFirstString.length(); i++){
        if(alphaFirstString.charAt(i) != alphaSecondString.charAt(i))
            return false;
    }
    return true;

This seems overly complicated. Consider either

    for (int i = 0; i < alphaFirstString.length(); i++){
        if (charFirstString[i] != charSecondString[i]) {
            return false;
        }
    }

    return true;

or

    String alphaFirstString = new String(charFirstString);
    String alphaSecondString  = new String(charSecondString);

    return alphaFirstString.equals(alphaSecondString);

Turning a perfectly handy random access array into a String just to process them letter by letter is a waste of time. Letter by letter processing is easier with the arrays. Or use the built-in for the strings. Or use @rolfl's suggestion of Arrays.equals, which worries about these fiddly problems for you.

Now, the time complexity here is going to be dominated by the sort. If you want to improve, you need to stop sorting. The alternative solution here is instead of sorting, to count the letters in the first word and then the second word.

    int[] counts = new int[CHARSET_SIZE];
    for (char letter : firstString.toCharArray()) {
        counts[letter]++;
    }

    for (char letter : secondString.toCharArray()) {
        counts[letter]--;
    }

    for (int count : counts) {
        if (count != 0) {
            return false;
        }
    }

    return true;

This would be linear in the sum of the string sizes and the size of the character set.

I haven't tested this, so you might have to cast letter to int to get this to work.

Answer 4

Everyone's answers have covered almost every comment I would have, I just would add a null check at the beginning to avoid NPE.

if (first == null || second == null) {
    throw new Exception("first and second cannot be null");
}