1. Understand the problem

• We are given two strings s and t.

• We need to check if t is an anagram of s — meaning both have the same letters with the same frequencies, just possibly in different orders.

2. Ask clarify questions

• Are both strings lowercase English letters only?

• What should we return — boolean True/False?

• Can the strings be empty?

• Should we consider spaces or punctuation (e.g., “a gentleman” vs “elegant man”)?

• What time complexity is expected — O(n)?

3. Work through examples

Example 1: s = “anagram”, t = “nagaram” → ✅ True

Example 2: s = “rat”, t = “car” → ❌ False

Example 3: s = “”, t = “” → ✅ True

Example 4: s = “aacc”, t = “ccac” → ❌ False (same letters but different counts)

4. Brainstorm 2–3 solutions

1. Naive solution (O(n²)):

• For each character in s, find and remove it from t. Slow for large strings.

1. Optimized (O(n log n)):

• Sort both strings and compare → sorted(s) == sorted(t)

1. Most optimized (O(n)):

• Count frequency of each character using a hash map or array (since characters are limited).

• Compare the counts.

5. Implement solution

5.1. Sorting

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False

        return sorted(s) == sorted(t)

• Time complexity: O(nlogn + mlogm).

• Space complexity: O(1) and O(m + n)

5.2. Hash Map

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False

        countS, countT = {}, {}

        for i in range(len(s)):
            countS[s[i]] = 1 + countS.get(s[i], 0)
            countT[t[i]] = 1 + countT.get(t[i], 0)
        return countS == countT

• Time complexity: O(n + m).

• Space complexity: O(1) and O(m + n)

5.3. Hash Table (26 items)

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False

        count = [0] * 26
        for i in range(len(s)):
            count[ord(s[i]) - ord('a')] += 1
            count[ord(t[i]) - ord('a')] -= 1

        for val in count:
            if val != 0:
                return False
        return True

• Time complexity: O(n + m).

• Space complexity: O(26 * 2)

6. Test your code

• Example: s = “anagram”, t = “nagaram”

• Step count map

After s loop {'a':3, 'n':1, 'g':1, 'r':1, 'm':1}
After t loop all counts → 0

✅ Returns True

• Time: O(n)

• Space: O(1) (limited alphabet)