Valid Anagram easy

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.

Example 1:

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

Example 2:

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

Steps

1. Check for Length: If the lengths of s and t are different, they cannot be anagrams, so return false.

2. Character Counting: Create a dictionary (or hash map) to store the frequency of each character in string s. Iterate through s, and for each character, increment its count in the dictionary.

3. Compare Frequencies: Iterate through string t. For each character in t, check if it exists as a key in the dictionary. If it doesn't, return false. If it does, decrement its count. If the count becomes 0, remove the key from the dictionary.

4. Empty Dictionary: After processing t, if the dictionary is empty, it means all characters in t were found in s with the same frequency, indicating an anagram. Return true. Otherwise, return false.

Explanation

The solution leverages the fact that anagrams have the same characters with the same frequencies. By counting character frequencies in s and then verifying those frequencies against t, we efficiently determine if they are anagrams. Using a dictionary provides O(1) average-case lookup time, making the overall approach efficient.

Code

using System;
using System.Collections.Generic;

public class Solution {
    public bool IsAnagram(string s, string t) {
        // Check for length difference
        if (s.Length != t.Length) {
            return false;
        }

        // Character frequency counting for s
        Dictionary<char, int> charCount = new Dictionary<char, int>();
        foreach (char c in s) {
            if (charCount.ContainsKey(c)) {
                charCount[c]++;
            } else {
                charCount[c] = 1;
            }
        }

        // Compare frequencies with t
        foreach (char c in t) {
            if (!charCount.ContainsKey(c)) {
                return false; 
            }
            charCount[c]--;
            if (charCount[c] == 0) {
                charCount.Remove(c);
            }
        }

        // If dictionary is empty, it's an anagram
        return charCount.Count == 0;
    }
}

Complexity

• Time Complexity: O(n), where n is the length of the strings. We iterate through each string once.
• Space Complexity: O(n) in the worst case, as the dictionary could store up to n unique characters (if all characters are unique). In the best case (all characters are the same), the space complexity would be O(1).