Valid Anagram

Problem Overview

The Valid Anagram problem from LeetCode asks you to determine whether two given strings are anagrams of each other.

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 another word or phrase, typically using all the original letters exactly once.

Example:

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

• Output: true

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

• Output: false

Solution Approach

C# Solution - Using Dictionary

The optimal approach using a Dictionary to count character frequencies:

public class Solution {
    public bool IsAnagram(string s, string t) {
        if(s.Length != t.Length) return false;

        var count = new Dictionary<char, int>();

        foreach(char c in s) {
            if(count.ContainsKey(c)){
                count[c]++;
            }else{
                count[c] = 1;
            }
        }

        foreach(char c in t) {
            if(!count.ContainsKey(c)) return false;

            count[c]--;

            if(count[c] < 0) return false;
        }

        return true;
    }
}

Time Complexity: O(n) - single pass through both strings Space Complexity: O(1) - at most 26 lowercase letters in the dictionary

Key Insights

1. Length Check: If strings have different lengths, they cannot be anagrams
2. Character Frequency: Both strings must have exactly the same characters with the same frequencies
3. Case Sensitivity: The problem typically considers lowercase letters
4. Constraint: Usually assumes strings contain only lowercase English letters

Related Problems

• Anagram groups (grouping anagrams together)
• Word pattern matching
• Permutation checking

Video Tutorial

Watch the complete explanation and walkthrough in the video above for a detailed solution approach and implementation details.