2.Valid Anagram

EasyBlind 75Arrays & Hashing · 2/9

Problem

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

An anagram uses exactly the same letters as the original, with exactly the same counts, just possibly in a different order. So "listen" and "silent" are anagrams, but "aab" and "abb" are not (the counts of a and b differ).

Examples

Input:  s = "anagram", t = "nagaram"
Output: true
Explanation: Both strings contain a×3, n×1, g×1, r×1, m×1.

Input:  s = "rat", t = "car"
Output: false
Explanation: s has a 't' that t does not, and t has a 'c' that s does not.

Input:  s = "ab", t = "a"
Output: false
Explanation: Different lengths can never be anagrams.

Constraints

1 <= s.length, t.length <= 5 * 10^4
s and t consist of lowercase English letters.

💡 Key Insight

Two strings are anagrams exactly when they have the same character frequencies. You can compare frequencies by sorting both strings (equal multisets sort to the same string) or, faster, by counting. Because the alphabet is only 26 lowercase letters, a fixed int[26] array counts in O(1) space: increment for s, decrement for t, and every slot must return to zero.

Brute Force

TimeO(n²)SpaceO(n)

Intuition

For each character of s, find a matching unused character in t and cross it off. If some character of s has no partner left in t, the strings are not anagrams. If lengths are equal and every character found a partner, they are.

Algorithm

If s.length() != t.length(), return false.
Copy t into a char[] remaining.
For each character c in s:
- Scan remaining for an index holding c. If found, overwrite it with a sentinel (e.g. '#') so it cannot be reused.
- If not found, return false.
Return true.

Visualization

s = "rat", t = "car"
remaining = [c, a, r]

c='r' → found at idx 2 → [c, a, #]
c='a' → found at idx 1 → [c, #, #]
c='t' → not found        → return false

Code

java

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        char[] remaining = t.toCharArray();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            boolean matched = false;
            for (int j = 0; j < remaining.length; j++) {
                if (remaining[j] == c) {
                    remaining[j] = '#'; // cross it off so it cannot be reused
                    matched = true;
                    break;
                }
            }
            if (!matched) {
                return false;
            }
        }
        return true;
    }
}

Complexity

Time: O(n²) — for each of the n characters of s we may scan all of t.
Space: O(n) — the copy of t.

Sorting

TimeO(n log n)SpaceO(n)

Intuition

Sorting arranges characters in a canonical order. Two strings with identical character counts produce the identical sorted string, and two strings with different counts cannot.

Algorithm

If the lengths differ, return false.
Convert both strings to char[] and sort them.
Return Arrays.equals(sortedS, sortedT).

Visualization

s = "anagram" → sort → a a a g m n r
t = "nagaram" → sort → a a a g m n r
                       identical → true

Code

java

import java.util.Arrays;

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        char[] a = s.toCharArray();
        char[] b = t.toCharArray();
        Arrays.sort(a);
        Arrays.sort(b);
        return Arrays.equals(a, b); // same multiset of letters ⇔ same sorted order
    }
}

Complexity

Time: O(n log n) — sorting both arrays.
Space: O(n) — toCharArray creates copies of both strings.

Frequency Count ArrayOptimal

TimeO(n)SpaceO(1)

Intuition

Keep one counter per letter. Walk both strings together: each character in s adds one to its letter's counter and each character in t subtracts one. If the strings are anagrams, every addition is cancelled by a subtraction and all 26 counters end at 0. Any non-zero counter means one string has more of that letter than the other.

Algorithm

If the lengths differ, return false.
Create int[] count = new int[26].
For each index i: count[s.charAt(i) - 'a']++ and count[t.charAt(i) - 'a']--.
If any count[k] != 0, return false; otherwise return true.

Dry Run

flowchart LR
    A["s = rat, t = car<br/>count all 0"] -->|"i=0: +r, -c"| B["r:1, c:-1"]
    B -->|"i=1: +a, -a"| C["r:1, c:-1, a:0"]
    C -->|"i=2: +t, -r"| D["r:0, c:-1, t:1"]
    D --> E{"all counts zero?"}
    E -->|"no: c=-1, t=1"| F["return false"]

Code

java

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        int[] count = new int[26]; // one slot per lowercase letter
        for (int i = 0; i < s.length(); i++) {
            count[s.charAt(i) - 'a']++; // letter supplied by s
            count[t.charAt(i) - 'a']--; // letter consumed by t
        }
        for (int c : count) {
            if (c != 0) {
                return false; // some letter appears a different number of times
            }
        }
        return true;
    }
}

Complexity

Time: O(n) — one pass over the strings plus a fixed 26-slot scan.
Space: O(1) — the counter array always has 26 entries regardless of input size.

Complexity Comparison

Approach	Time	Space
Brute Force	O(n²)	O(n)
Sorting	O(n log n)	O(n)
Frequency Count Array	O(n)	O(1)

Common Pitfalls

Forgetting the length check — "a" vs "ab" would otherwise slip through the brute force, and in the counting approach t.charAt(i) would go out of bounds.
Comparing sorted arrays with == instead of Arrays.equals — == compares references, not contents.
For the Unicode follow-up, an int[26] no longer works; switch to a HashMap<Character, Integer> (or int[] sized to the code-point range).
Only checking that every letter of s appears in t (a set check) ignores counts — "aab" and "abb" would be wrongly accepted.