Valid Anagram

Problem Summary

(Write in your own words, not copied from LeetCode. This forces comprehension.)

• Two string are given
• Determine if they are anagram (same characters but different arrangements)

What is Being Asked?

(One sentence on the actual task.)

• Two strings have the same number and same characters

Key Observations

(Patterns, constraints, or hints in the problem statement.)

• Length should be the same
• Count of each character should be the same

Approach Taken

(Step-by-step logic or pseudocode before coding.)

• False if length is different
• Count each character for both strings
• Compare the counts to each other
• True if both are same

Why This Works

(Explain the core reason the solution is correct.)

• We are comparing whether both strings are made of the same exact characters but are in different order

Main Concepts Used

(Mark the CS concepts or algorithms used.)

• Hash Map

Time & Space Complexity

• Time: O(N) → Reason: Iterating through the array once together
• Space: O(1) → Reason: Input consists of lowercase English letters, finite set so we will maximum store 26 characters

Code

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        letter_to_count_in_s = {} # a: 3, n: 1, g: 1, r: 1, m: 1
        letter_to_count_in_t = {} # n: 1, a: 3, g: 1, r: 1, m: 1

        if len(s) != len(t):
            return False

        # s = anagram
        # t = nagaram
        # a,n
        for letter_in_s, letter_in_t in zip(s, t):
            letter_to_count_in_s[letter_in_s] = letter_to_count_in_s.get(letter_in_s, 0) + 1
            letter_to_count_in_t[letter_in_t] = letter_to_count_in_t.get(letter_in_t, 0) + 1

        return letter_to_count_in_s == letter_to_count_in_t
    # time: O(n)
    # space: O(1)