Course4all
Join us on telegram
Home/dsa/Arrays & Hashing/Valid Anagram

Valid Anagram

Master this topic with zero to advance depth.

Valid Anagram

Given two strings s and t, return true if t is an anagram of s, and false otherwise. An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Visual Representation

s = "anagram", t = "nagaram" Method: Count each character a: 3, n: 1, g: 1, r: 1, m: 1 (in s) a: 3, n: 1, g: 1, r: 1, m: 1 (in t) Counts Match -> True
Easy

Examples

Input: s = "anagram", t = "nagaram"
Output: true
Input: s = "rat", t = "car"
Output: false
Approach 1

Level I: Sorting

Intuition

Anagrams have the same characters in the same frequency. If we sort both strings, they should be identical.

⏱ O(N log N) where N is string length.💾 O(1) or O(N) depending on sort implementation.

Detailed Dry Run

s="abc", t="cba" s.sort() -> "abc" t.sort() -> "abc" "abc" == "abc" -> True

java
import java.util.Arrays;
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);
    }
}
Approach 2

Level II: HashMap (Character Count)

Intuition

Count character frequencies using a HashMap. This handles Unicode characters more naturally than a fixed-size array.

⏱ O(N)💾 O(1) - finite character set size.

Detailed Dry Run

s="aa", t="a" Map {a: 2} from s Map {a: 2-1=1} from t Length mismatch detected early -> return False

java
import java.util.*;
class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) return false;
        Map<Character, Integer> count = new HashMap<>();
        for (char x : s.toCharArray()) count.put(x, count.getOrDefault(x, 0) + 1);
        for (char x : t.toCharArray()) {
            if (!count.containsKey(x) || count.get(x) == 0) return false;
            count.put(x, count.get(x) - 1);
        }
        return true;
    }
}
Approach 3

Level III: Fixed-Size Array (Optimal)

Intuition

Since we only have 26 lowercase letters, an array of size 26 is more efficient than a HashMap.

⏱ O(N)💾 O(1) - fixed 26 integers.

Detailed Dry Run

arr = [0]*26 s="a": arr[0]++ -> [1,0...] t="a": arr[0]-- -> [0,0...] All indices zero -> True

java
class Solution {
    public boolean isAnagram(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;
    }
}
← Previous QuestionTwo Sum
Next Question →Contains Duplicate