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 Lengths: First, we check if the lengths of the two input strings s and t are equal. If they are not equal, they cannot be anagrams, so we return False.

2. Character Counting: We'll use a dictionary (or hash map) to count the frequency of each character in string s. For each character in s, we increment its count in the dictionary.

3. Comparing Frequencies: We then iterate through string t. For each character in t, we decrement its count in the dictionary. If a character is not found in the dictionary (meaning it's not in s), or if its count becomes negative (meaning t has more occurrences than s), we return False.

4. Final Check: After iterating through t, if all character counts in the dictionary are 0, it means the character frequencies in s and t are identical, and therefore they are anagrams. We return True.

Explanation

The core idea is to efficiently compare the character frequencies of the two strings. Using a dictionary provides O(1) average-case time complexity for lookups and updates, making the algorithm efficient. The algorithm systematically checks if each character's frequency matches between the two strings. If any discrepancy is found, it immediately indicates that the strings are not anagrams, avoiding unnecessary processing.

Code

from collections import defaultdict

def isAnagram(s: str, t: str) -> bool:
    """
    Checks if two strings are anagrams of each other.

    Args:
        s: The first string.
        t: The second string.

    Returns:
        True if t is an anagram of s, False otherwise.
    """
    if len(s) != len(t):
        return False

    char_counts = defaultdict(int)  # Use defaultdict for easier handling of missing keys

    # Count character frequencies in s
    for char in s:
        char_counts[char] += 1

    # Check character frequencies in t
    for char in t:
        char_counts[char] -= 1
        if char_counts[char] < 0:  #If count goes below zero means t has more of a character than s
            return False

    # If all counts are 0, it's an anagram
    return all(count == 0 for count in char_counts.values())

Complexity

• Time Complexity: O(n), where n is the length of the strings. We iterate through the strings once each.
• Space Complexity: O(1) in the average case. The dictionary char_counts will store at most 26 entries (for lowercase English letters), making the space usage constant regardless of input string size. In the worst case(all unique characters) it becomes O(n) but that's unlikely in the problem context.