Valid Anagram

Given two lowercase strings s and t, return true if t is an anagram of s: the characters of s can be rearranged to form t.

LeetCode: 242. Valid Anagram

Example

Input:  "afteracademy", "academyafter"    Output: true
Input:  "rat", "car"                      Output: false

Brute force: sort both strings

Anagrams become the same string once their characters are sorted. String.toCharArray returns a copy of the characters, so sorting it leaves the original string unchanged (a String is immutable).

import java.util.Arrays;

public class Main {
    static boolean isAnagram(String s, String t) {
        char[] a = s.toCharArray();
        char[] b = t.toCharArray();
        Arrays.sort(a);
        Arrays.sort(b);
        return Arrays.equals(a, b);
    }

    public static void main(String[] args) {
        System.out.println(isAnagram("afteracademy", "academyafter") + " " + isAnagram("rat", "car"));
    }
}

true false

Time: O(n log n). Space: O(n).

Optimal: count the letters

With only 26 possible letters, an array works as the hash table. Add 1 for each letter of s, subtract 1 for each letter of t, and check that every count is back to 0. The index of a letter is c - 'a', because char values are numbers.

public class Main {
    static boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) return false;
        int[] counts = new int[26];
        for (int i = 0; i < s.length(); i++) {
            counts[s.charAt(i) - 'a']++;
            counts[t.charAt(i) - 'a']--;
        }
        for (int c : counts) {
            if (c != 0) return false;
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(isAnagram("afteracademy", "academyafter") + " " + isAnagram("rat", "car"));
        System.out.println(isAnagram("a", "ab") + " " + isAnagram("", ""));
    }
}

true false
false true

Time: O(n). Space: O(1): the array has 26 entries no matter how long the strings are.

For arbitrary Unicode text, count characters in a HashMap<Character, Integer> instead, using merge(c, 1, Integer::sum). The same idea applies, with O(k) space for k distinct characters. A char is a 16-bit code unit, so characters outside the Basic Multilingual Plane need String.codePoints() to be counted as one character each.

Edge cases

• Different lengths: can't be anagrams.
• Empty strings: anagrams of each other.
• Same letters, different counts ("aab", "abb"): the counts don't cancel out.