☕ DSA Java Articles

Topics › Strings › Basic and Easy String Problems

Check if two strings are anagram of each other

Easy TUF ID 2809 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

Two strings are anagrams of each other if one can be rearranged into the other, that is, they contain exactly the same characters with exactly the same multiplicities. Given two strings s and t, return true if they are anagrams and false otherwise.

Constraints: 0 ≤ |s|, |t| ≤ 5 × 10^4; lowercase English letters in the classic version. Two of the three approaches below work for any alphabet; the third is specialised to lowercase letters and is the one interviewers usually expect.

Example 1

s = "anagram", t = "nagaram"
answer = true          // both have a×3, g, m, n, r

Example 2

s = "rat", t = "car"
answer = false         // t has a c that s does not, and s has a t that t does not

Example 3

s = "aacc", t = "ccac"
answer = false         // same set of letters {a, c}, but a appears twice in s and once in t

Approach 1: Brute force, sort and compare

Intuition. Two multisets are equal exactly when their sorted sequences are equal. Sorting puts both strings in a canonical form, so if s and t are anagrams they sort to the same string, and if they are not, the sorted forms differ somewhere. This sidesteps counting entirely.

Algorithm.

  1. If the lengths differ, return false.
  2. Convert both strings to char[] and sort each.
  3. Return Arrays.equals(a, b).
static boolean bruteForce(String s, String t) {
    if (s.length() != t.length()) return false;
    char[] a = s.toCharArray(), b = t.toCharArray();
    Arrays.sort(a);
    Arrays.sort(b);
    return Arrays.equals(a, b);
}

Complexity. Time O(n log n) for the two sorts. Space O(n) for the two character arrays (Java strings are immutable, so sorting needs a copy).

This is “brute force” only relative to the linear solutions below; it is a perfectly good answer and is the most natural one when the alphabet is unknown or huge, because it needs no assumption about which characters can appear.

Approach 2: Better, a hash map of counts

Intuition. Anagrams have identical character counts, so count the characters of s, then walk through t and consume the counts. If t ever needs a character whose count is already zero, the strings are not anagrams. Because the lengths are equal, finishing the walk through t without failure means every count was used up exactly. Removing a key when its count hits zero keeps the map honest: at the end, it must be empty.

Algorithm.

  1. If the lengths differ, return false.
  2. For each character c of s, increment count[c].
  3. For each character c of t: if count has no entry for c, return false; if the entry is 1, remove it; otherwise decrement it.
  4. Return count.isEmpty().
static boolean better(String s, String t) {
    if (s.length() != t.length()) return false;
    Map<Character, Integer> count = new HashMap<>();
    for (char c : s.toCharArray()) count.merge(c, 1, Integer::sum);
    for (char c : t.toCharArray()) {
        Integer left = count.get(c);
        if (left == null) return false;                    // t has a character s does not have (any more)
        if (left == 1) count.remove(c); else count.put(c, left - 1);
    }
    return count.isEmpty();
}

Complexity. Time O(n) with constant-time map operations on average. Space O(k) where k is the number of distinct characters.

count.merge(c, 1, Integer::sum) is the idiomatic way to increment a counter in a Map<Character, Integer>: it inserts 1 if the key is absent and otherwise applies Integer::sum to the old value and 1. The char argument is autoboxed to Character, so the lookups in the second loop find the same keys.

Since the lengths are equal, the final count.isEmpty() is always true once the second loop completes: t consumed exactly n units from a map that held exactly n units. Keeping the check costs nothing and makes the method correct even if someone removes the length guard.

Approach 3: Optimal, one frequency array

Intuition. When the alphabet is the 26 lowercase letters, a HashMap is overkill. An int[26] indexed by c - 'a' is a perfect hash with no collisions and no boxing. Even better, we can process both strings in the same loop: add one for the character of s at position i and subtract one for the character of t at position i. The strings are anagrams exactly when every entry ends at zero, meaning each letter was added and subtracted the same number of times.

Algorithm.

  1. If the lengths differ, return false.
  2. Create freq[26], all zero.
  3. For each i: freq[s[i] - 'a']++ and freq[t[i] - 'a']--.
  4. Return true if every entry of freq is 0, else false.
static boolean optimal(String s, String t) {
    if (s.length() != t.length()) return false;
    int[] freq = new int[26];
    for (int i = 0; i < s.length(); i++) {
        freq[s.charAt(i) - 'a']++;
        freq[t.charAt(i) - 'a']--;
    }
    for (int f : freq) if (f != 0) return false;
    return true;
}

Dry run on s = "aacc", t = "ccac":

i s[i] t[i] freq[a] freq[c]
0 a c 1 -1
1 a c 2 -2
2 c a 1 -1
3 c c 1 -1

freq[a] = 1 and freq[c] = -1 are non-zero, so the answer is false. On "anagram"/"nagaram" every entry returns to zero and the answer is true.

Complexity. Time O(n + 26) = O(n). Space O(1): 26 integers whatever the input size.

The single-loop form relies on the length check: with strings of different lengths, t.charAt(i) would run out of bounds, and even if it did not, a shorter t could leave positive counts that look like a mismatch for the wrong reason.

Edge cases and pitfalls