Valid Anagram

NeetCode: Valid Anagram · LeetCode: 242. Valid Anagram · Difficulty: Easy

Given two strings s and t, return true if t is an anagram of s: it uses exactly the same letters with the same counts, in any order. Both strings contain lowercase English letters.

Example

Text

Input:  s = "racecar", t = "carrace"    Output: true
Input:  s = "jar",     t = "jam"        Output: false

Brute force: sort both strings

A Java String is immutable, so the code copies each one into a char[] and sorts the copies. Arrays.sort on a char[] is O(n log n); Arrays.equals compares two arrays element by element.

Two strings are anagrams exactly when their sorted characters are equal.

Java

import java.util.Arrays;

public class Main {
    static class Solution {
        public 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) {
        Solution sol = new Solution();
        System.out.println(sol.isAnagram("racecar", "carrace"));
        System.out.println(sol.isAnagram("jar", "jam"));
    }
}

Output

true
false

Time: O(n log n). Space: O(n) for the two char[] copies.

Optimal: count letters

Only 26 letters are possible, so a fixed int[26] of counters is enough. In Java, char is a number, so 'c' - 'a' is an int from 0 to 25 and works as an array index. Add one for each letter of s and subtract one for each letter of t. If the strings are anagrams, every counter ends at zero. Different lengths can never match, so check that first.

Java

public class Main {
    static class Solution {
        public 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) {
        Solution sol = new Solution();
        System.out.println(sol.isAnagram("racecar", "carrace"));
        System.out.println(sol.isAnagram("jar", "jam"));
        System.out.println(sol.isAnagram("ab", "abc"));
    }
}

Output

true
false
false

Time: O(n). Space: O(1), because the array has a fixed size of 26.

If the input could contain any Unicode text, use a HashMap<Character, Integer> instead of the array (and compare the counts with equals, not ==). The idea is identical.