Valid Anagram

Easystringhash-tablesorting
Category: Array & Hashing
Companies that ask this question:
AmazonFacebookBloombergGoogle
LeetCode →NeetCode →

Approach

Valid Anagram

Problem Statement

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.

Approach 1: Hash Map (Frequency Count)

Count character frequencies and compare.

Algorithm

  1. Check lengths: If different, not an anagram
  2. Count frequencies: Use hash map for string s
  3. Verify against t: Decrement counts for string t
  4. Check zeros: All counts should be zero

Time Complexity

  • Time: O(n) where n is string length
  • Space: O(1) - at most 26 characters for lowercase English

Example

s = "anagram", t = "nagaram"

Frequency map of s:
a: 3, n: 1, g: 1, r: 1, m: 1

Check t:
n: 3->2, a: 1->0, g: 1->0, a: 0->-1... 
Wait, process correctly:
All frequencies match! Return true

Approach 2: Sorting

Sort both strings and compare.

Algorithm

  1. Sort both strings
  2. Compare sorted strings
  3. Return equality result

Time Complexity

  • Time: O(n log n) for sorting
  • Space: O(1) or O(n) depending on implementation

Key Insights

  1. Hash map is more efficient: O(n) vs O(n log n)
  2. Only 26 lowercase letters → fixed space
  3. Early exit if lengths differ
  4. Can use array instead of hash map for ASCII

Solution

java
1/**
2 * Valid Anagram
3 * Time: O(n), Space: O(1)
4 */
5
6import java.util.*;
7
8class Solution {
9    public boolean isAnagram(String s, String t) {
10        if (s.length() != t.length()) {
11            return false;
12        }
13        
14        int[] count = new int[26];
15        
16        for (int i = 0; i < s.length(); i++) {
17            count[s.charAt(i) - 'a']++;
18            count[t.charAt(i) - 'a']--;
19        }
20        
21        for (int c : count) {
22            if (c != 0) return false;
23        }
24        
25        return true;
26    }
27}
28
29// Sorting approach
30class Solution2 {
31    public boolean isAnagram(String s, String t) {
32        if (s.length() != t.length()) {
33            return false;
34        }
35        
36        char[] sChars = s.toCharArray();
37        char[] tChars = t.toCharArray();
38        Arrays.sort(sChars);
39        Arrays.sort(tChars);
40        
41        return Arrays.equals(sChars, tChars);
42    }
43}
44
Loading visualizer...