☕ DSA Java Articles

Topics › Strings › Basic and Easy String Problems

Valid Anagram

Easy TUF ID 400 SDEBlind 75

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

Given two strings s and t, return true if t is an anagram of s: a rearrangement that uses every character of s exactly as many times as s does, and nothing else. Otherwise return false.

Constraints: 1 ≤ |s|, |t| ≤ 5 · 10^4, lowercase English letters. A follow-up asks what changes if the strings may contain arbitrary Unicode characters; that is answered at the end. The Java methods also accept empty strings (two empty strings are anagrams).

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' and no 't'

Example 3

s = "aacc", t = "ccac"
answer = false       // same letters, different counts: a×2 c×2 vs a×1 c×3

The third example is why “same set of letters” is not enough. Anagrams must agree on the multiset: every letter with its count.

Approach 1: Brute force, cross letters off

Intuition. This is how you would check by hand with letter tiles. For each letter of s, look through t for a matching tile that has not been used yet and set it aside. If some letter of s finds no unused partner, the answer is false. If the lengths are equal and every letter of s found a partner, then every tile of t was used exactly once, so the two are anagrams.

The length check up front matters: without it, s = "a", t = "ab" would pass, because every letter of s finds a partner even though t has a leftover b.

Algorithm.

  1. If the lengths differ, return false.
  2. Keep a used flag for each position of t.
  3. For each character of s, find the first unused equal character in t and mark it used. If none exists, return false.
  4. Return true.
static boolean bruteForce(String s, String t) {
    if (s.length() != t.length()) return false;
    boolean[] used = new boolean[t.length()];
    for (int i = 0; i < s.length(); i++) {
        boolean found = false;
        for (int j = 0; j < t.length(); j++) {
            if (!used[j] && t.charAt(j) == s.charAt(i)) {
                used[j] = true;                     // this letter of t is now spent
                found = true;
                break;
            }
        }
        if (!found) return false;
    }
    return true;
}

Complexity. Time O(n^2): for each of n letters we may scan all of t. Space O(n) for the flags.

For n = 5 · 10^4 that is over a billion steps in the worst case. The problem is that we search for each partner from scratch instead of organising t once.

Approach 2: Better, sort both strings

Intuition. Sorting puts the letters of a string in a canonical order that depends only on which letters it has and how many of each, not on where they were. Two strings are anagrams exactly when they have the same letters with the same counts, so they are anagrams exactly when their sorted forms are equal. "anagram" and "nagaram" both sort to "aaagmnr".

Algorithm.

  1. If the lengths differ, return false.
  2. Sort the characters of both strings.
  3. Return whether the sorted arrays are equal.
static boolean better(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 character arrays, since Java strings are immutable and must be copied before sorting.

This is a perfectly good answer when code clarity matters more than the last factor of speed, and it works unchanged for any characters that can be compared, with one Unicode subtlety discussed below.

Approach 3: Optimal, one array of counters

Intuition. Sorting computes far more than we need. We do not care about the order of letters at all, only their counts, and with a 26-letter alphabet the counts fit in a fixed array. Walk both strings together: add one for each letter of s and subtract one for each letter of t. A counter ends at zero exactly when that letter appears equally often in both strings, so the strings are anagrams exactly when every counter ends at zero.

Using a single array with +1 and -1 (instead of two arrays compared at the end) halves the memory and keeps the final check to one loop.

Algorithm.

  1. If the lengths differ, return false.
  2. For each index i, do count[s[i] - 'a']++ and count[t[i] - 'a']--.
  3. Return false if any counter is non-zero, otherwise true.
static boolean optimal(String s, String t) {
    if (s.length() != t.length()) return false;
    int[] count = new int[26];
    for (int i = 0; i < s.length(); i++) {
        count[s.charAt(i) - 'a']++;
        count[t.charAt(i) - 'a']--;
    }
    for (int c : count) {
        if (c != 0) return false;
    }
    return true;
}

Dry run on s = "rat", t = "car":

i s[i] t[i] non-zero counters after this step
0 r c r = +1, c = -1
1 a a r = +1, c = -1 (a went +1 then -1)
2 t r c = -1, t = +1

Two counters are non-zero at the end, so the answer is false.

Complexity. Time O(n): one pass over the strings and one pass over 26 counters. Space O(1): the array has 26 entries no matter how long the strings are.

Follow-up: Unicode input

With arbitrary Unicode text, a fixed 26-slot array no longer works, so replace it with a HashMap from character to count. There is one more trap specific to Java. A char is a UTF-16 code unit, not a character: symbols outside the Basic Multilingual Plane, such as most emoji, are stored as two chars (a surrogate pair). Counting chars can then be fooled. The strings made of U+1F600 followed by U+1F300, and of U+1F700 followed by U+1F200, contain exactly the same four UTF-16 code units, so the sorting approach above says true. But they are made of four completely different symbols, so the right answer is false. The Java file contains this exact test.

The fix is to count code points with String.codePoints(), which joins each surrogate pair back into one symbol:

static boolean unicode(String s, String t) {
    Map<Integer, Integer> count = new HashMap<>();
    s.codePoints().forEach(cp -> count.merge(cp, 1, Integer::sum));
    for (int cp : t.codePoints().toArray()) {
        Integer c = count.get(cp);
        if (c == null) return false;                // t uses a symbol s has run out of
        if (c == 1) count.remove(cp);
        else count.put(cp, c - 1);
    }
    return count.isEmpty();                         // anything left over appears in s but not in t
}

Complexity. Time O(n) on average (hash map operations). Space O(k) for k distinct symbols.

Even code points are not the end of the story for human text: "é" can be written as one code point (U+00E9) or as e followed by a combining accent (U+0301). If those should count as the same letter, normalise both strings first (Java has java.text.Normalizer for this).

Edge cases and pitfalls