Valid Anagram

📌 Problem Statement

Given two strings s and t, return true if t is an anagram of s, and false otherwise.

🧠 What is an Anagram?

An anagram is a word or phrase formed by rearranging the letters of another.
For example:

• "anagram" and "nagaram" are anagrams ✅

• "rat" and "car" are not ❌

✅ Constraints

• Both strings consist of lowercase English letters only.

• Their length is between 1 and 50,000 characters.

🧭 Approach 1: Sorting

💡 Idea

If two strings are anagrams, sorting them should give the same result.

🧾 Steps

1. If lengths of s and t are not equal → return false.

2. Sort both strings.

3. Compare them.

bool isAnagram(string s, string t) {
    if (s.length() != t.length()) return false;
    sort(s.begin(), s.end());
    sort(t.begin(), t.end());
    return s == t;
}

🧪 Time & Space

• Time: O(n log n) (due to sorting)

• Space: O(1) extra (if sorting in-place)

🥇 Approach 2: Optimal Hashing (Using Frequency Count)

💡 Idea

Count how many times each letter appears in s and t. If all counts match, they're anagrams.

🧾 Steps

1. If lengths differ → return false.

2. Create an integer array of size 26 (for letters a–z).

3. For every character in s, increment count.

4. For every character in t, decrement count.

5. If all counts are zero → they are anagrams.

#include <algorithm> // for transform
#include <cctype>    // for tolower

bool isAnagram(string s, string t) {
    if (s.length() != t.length()) return false;

    // Convert to lowercase to handle upper/lowercase
    transform(s.begin(), s.end(), s.begin(), ::tolower);
    transform(t.begin(), t.end(), t.begin(), ::tolower);

    int count[26] = {0};
    for (int i = 0; i < s.length(); i++) {
        count[s[i] - 'a']++;
        count[t[i] - 'a']--;
    }

    for (int i = 0; i < 26; i++) {
        if (count[i] != 0) return false;
    }

    return true;
}

🧪 Time & Space

• Time: O(n)

• Space: O(1) (fixed 26-letter count array)

problem link: https://leetcode.com/problems/valid-anagram/description/