Valid Anagram

Easy10–15 min

Topics

StringHash Table

Companies

AmazonGoogleMicrosoftBloomberg

Given two strings s and t, return true if t is an anagram of s, and false otherwise. Both strings consist only of lowercase English letters. Two strings are anagrams of each other only if they contain the exact same letters with the exact same frequency — order doesn't matter.

Test Case 1:

Input:s = "anagram", t = "nagaram"

Output:true

Explanation:Both strings contain the same letters with the same frequency, just rearranged.

Test Case 2:

Input:s = "rat", t = "car"

Output:false

Explanation:The letters don't match up — 'rat' has a 't' and 'r' that 'car' doesn't have.

Test Case 3:

Input:s = "a", t = "ab"

Output:false

Explanation:Different lengths can never be anagrams — t has an extra letter.

Constraints

◆1 ≤ s.length, t.length ≤ 5 × 10⁴
◆s and t consist of lowercase English letters only

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

🧪Try your own test case

s (string) — 1-16 lowercase letterst (string) — 1-16 lowercase letters

1	class Solution {
2	public boolean isAnagram(String s, String t) {
3	if (s.length() != t.length()) return false;
4	Map<Character, Integer> freq = new HashMap<>();
5	for (char c : s.toCharArray()) {
6	freq.put(c, freq.getOrDefault(c, 0) + 1);
7	}
8	for (char c : t.toCharArray()) {
9	if (!freq.containsKey(c) \|\| freq.get(c) == 0) return false;
10	freq.put(c, freq.get(c) - 1);
11	}
12	return true;
13	}
14	}
15

String

Variables

s.length3

t.length3

COMPARE

First, check that both strings are the same length. s has 3 characters, t has 3 — they match, so an anagram is still possible.

Step 1 / 18

Approach & Solutions

Brute Force — Sorting

Brute

Sort both strings alphabetically, then compare them character by character. If two strings contain exactly the same letters with the same frequency, sorting will line them up identically. Simple and correct, but the sort costs more than a single pass needs to.

TimeO(n log n)

SpaceO(n)

Java

Try it out

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) return false;
        char[] sArr = s.toCharArray();
        char[] tArr = t.toCharArray();
        Arrays.sort(sArr);
        Arrays.sort(tArr);
        return Arrays.equals(sArr, tArr);
    }
}

Optimal — Frequency Map

Optimal

Build a frequency map counting every character in s. Then walk through t, decrementing the count for each character you see. If a character in t is missing from the map, or its count is already zero, the strings can't be anagrams — bail out immediately. A single pass over each string, no sorting required.

TimeO(n)