Valid Anagram

LeetCode 242 | Difficulty: Easy

Easy

Problem Description

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

Example 1:

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

Output: true

Example 2:

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

Output: false

Constraints:

- `1 <= s.length, t.length <= 5 * 10^4`

- `s` and `t` consist of lowercase English letters.

Follow up: What if the inputs contain Unicode characters? How would you adapt your solution to such a case?

Topics: Hash Table, String, Sorting

---

Approach

Hash Map

Use a hash map for O(1) average lookups. Store seen values, frequencies, or indices. The key question: what should I store as key, and what as value?

When to use

Need fast lookups, counting frequencies, finding complements/pairs.

String Processing

Consider character frequency counts, two-pointer approaches, or building strings efficiently. For pattern matching, think about KMP or rolling hash. For palindromes, expand from center or use DP.

When to use

Anagram detection, palindrome checking, string transformation, pattern matching.

Sorting

Sort the input to bring related elements together or enable binary search. Consider: does sorting preserve the answer? What property does sorting give us?

When to use

Grouping, finding closest pairs, interval problems, enabling two-pointer or binary search.

---

Solutions

Solution 1: C# (Best: 148 ms)

Metric	Value
Runtime	148 ms
Memory	N/A
Date	2018-04-14

Solution

public class Solution {
    public bool IsAnagram(string s, string t) {
        Dictionary<char, int> oc = new Dictionary<char, int>();
    int m=s.Length, n = t.Length;
    if(m!=n) return false;
    for (int i = 0; i < m; i++)
    {
        if(oc.ContainsKey(s[i])){
            oc[s[i]]++;
        }
        else
        {
            oc.Add(s[i], 1);
        }
    }
    for (int j = 0; j < n; j++)
    {
        if(!oc.ContainsKey(t[j]))
        return false;
        if(oc[t[j]]==0) return false;
        oc[t[j]]--;
    }
    return true;
    }
}

📜 1 more C# submission(s)

Submission (2018-04-14) — 160 ms, N/A

public class Solution {
    public bool IsAnagram(string s, string t) {
        char[] sArr = s.ToCharArray();
        char[] tArr = t.ToCharArray();
        Array.Sort(sArr);
        Array.Sort(tArr);
        return new String(sArr).Equals(new string(tArr));
    }
}

---

Complexity Analysis

Approach	Time	Space
Sort + Process	$O(n log n)$	$O(1) to O(n)$
Hash Map	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Start by clarifying edge cases: empty input, single element, all duplicates.
• Hash map gives O(1) lookup — think about what to use as key vs value.