How to check if two Strings are Anagram of each other?

Problem Statement

Given two strings, s and t, determine if t is an anagram of s.

Definition of Anagram

An anagram is a word or phrase formed by rearranging the letters of another word or phrase, using all the original letters exactly once.

Example

For the strings s = "anagram" and t = "ganaram", the answer is true since they are anagrams of each other.

Brute Force Solution

One simple way to check for anagrams is to sort both strings and then compare them. If they’re the same after sorting, they are anagrams.

public class AnagramChecker {
    public static void main(String[] args) {
        String s = "anagram";
        String t = "ganaram";
        System.out.println(isAnagramBruteForce(s, t)); // Output should be true
    }

    public static boolean isAnagramBruteForce(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }

        char[] sArray = s.toCharArray();
        char[] tArray = t.toCharArray();
        
        Arrays.sort(sArray);
        Arrays.sort(tArray);
        
        return Arrays.equals(sArray, tArray);
    }
}

While this approach is simple to understand, sorting takes O(nlogn) time, making this solution less efficient for large strings.

Optimal Solution

Instead of sorting, we can count the occurrence of each character in both strings and compare these counts. If the counts match, the strings are anagrams.

To be an anagram, two strings must have the same characters and the same number of each character. So, the primary challenge here is to effectively count and compare the characters in both strings.

Here is the optimal solution in Java:

public class AnagramChecker {

    public static boolean isAnagramOptimal(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }

        int[] charCount = new int[26]; // Assuming only lowercase alphabets

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

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

Here, we utilize a single integer array of size 26 (for each letter of the alphabet) to count occurrences. The time complexity of this solution is O(n), making it more efficient for larger strings.

Intuition Behind Optimization:

Think of the counts as balancing weights. For s, we’re adding weights, and for t, we’re removing weights. If they’re anagrams, the scales should balance out to zero by the end.