242. Valid Anagram

Problem

Given two strings s and t, return true if t is an anagram of s, and false otherwise.

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

Explanation

First pass: brute force with sorting

My first idea was to check if the two strings have the same characters in the same quantities by sorting them. If both strings are anagrams, their sorted versions should be identical. I start by checking if they have different lengths—if they do, they can't be anagrams. Then I convert each string to a character array, sort both arrays, and compare if they're equal. This works and is simple to understand, but sorting takes O(n log n) time due to the sorting algorithm.

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) return false;
 
        char[] sChars = s.toCharArray();
        char[] tChars = t.toCharArray();
 
        java.util.Arrays.sort(sChars);
        java.util.Arrays.sort(tChars);
 
        return java.util.Arrays.equals(sChars, tChars);
    }
}

Final pass: HashMap for character frequency

To avoid the overhead of sorting, I switched to counting the frequency of each character in both strings using two HashMaps. I iterate through both strings at the same time, incrementing or initializing the count for each character. Once I've counted all characters, I compare if both maps are equal. If they are, both strings have the exact same characters with the same frequencies, meaning they're anagrams. This approach is more efficient with O(n) time complexity since I only iterate through each string once.

Time: O(n)
Space: O(1) - at most 26 lowercase letters in the HashMaps

Solution