Are Strings Anagrams?

Anagram = all letters can be reused to create another word.

Approaches

Approach 1: sorting (nonintuitive to me)

An anagram is produced by rearranging the letters.
Sort the letters alphabetically for the two strings.
The sorted strings should be equal!

public boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) {
        return false;
    }
    char[] str1 = s.toCharArray();
    char[] str2 = t.toCharArray();
    Arrays.sort(str1);
    Arrays.sort(str2);
    return Arrays.equals(str1, str2);
}

Time complexity : O(n log n).
Space complexity : O(1) but not in Java! toCharArray() makes a copy of the string so it costs O(n), but we ignore this for complexity analysis because:

It is a language dependent detail.
It depends on how the function is designed. For example, the function parameter types can be changed to char[].

Approach 2: counting technic (my favorite)

If the input is only letters from a-z, a simple counter table of size 26 is sufficient.
If you support the strict ASCII range, you need 128 characters.
For extended ASCII, it’s 256. See my answer here on StackOverflow.

For 26 letters only, there is a trick. You need to do -‘a’ so that you start from ‘a’.

int[] counter = new int[26];
    for (int i = 0; i < s.length(); i++) {
        counter[s.charAt(i) - 'a']++;
        counter[t.charAt(i) - 'a']--;
    }

    // Support for extended ASCII
   private boolean isAnagram(String a, String b) {
        if (a.length() != b.length()) {
            return false;
        }
        int[] lookup = new int[256];
        for (int i = 0; i < a.length(); i++) {
            lookup[a.charAt(i)]++;
        }
        // do not set isAagram by default because "b" and "" would be anagram otherwise
        int i = 0;
        while (i < b.length()) {
            lookup[b.charAt(i)]--;
            if (lookup[b.charAt(i)] >= 0) {
                i++;
            } else {
                break;
            }
        }
        return i >= b.length();
    }

Time complexity : O(n)
Space complexity : O(1). Although we do use extra space, the space complexity is O(1)O(1) because the table’s size stays constant no matter how large nn is.

Follow up

What if the inputs contain unicode characters? How would you adapt your solution to such a case?

Answer

Use a hash table instead of a fixed size counter. Imagine allocating a large size array to fit the entire range of unicode characters, which could go up to more than 1 million. A hash table is a more generic solution and could adapt to any range of characters.