1. Valid Anagram

Problem Statement

Given two strings s and t, determine whether t is an anagram of s.

Return true if it is an anagram, otherwise return false.

Pattern Used

Frequency Counting / Sorting

Approach (High-level)

• Sorting approach: Sort both strings and compare them

• Frequency table approach:

  Increment frequency for characters in s and decrement for t; if all counts are zero, strings are anagrams

Time & Space Complexity

• Sorting: O(n log n)
• Frequency Table: O(n)
• Space: O(1) (fixed-size frequency array)

LeetCode

• 242. Valid Anagram
• https://leetcode.com/problems/valid-anagram/

// m1(bruteForce):sort both the words and if s==t (it is a anagram)
/*
class Solution {
public:
    bool isAnagram(string s, string t) {
        sort(s.begin(),s.end());
        sort(t.begin(),t.end());

        return s==t;
    }
};*/

//  T.C =O( n log n + m log m)
class Solution {
public:
    bool isAnagram(string s, string t) {
        if (s.size() != t.size()) { // Check if lengths are different
            return false;
        }

        int freqTable[256] = {0}; // Assume ASCII characters only
        
        // Increment counts for `s` and decrement counts for `t`
        for (int i = 0; i < s.size(); i++) {
            freqTable[s[i]]++;
            freqTable[t[i]]--;
        }
        
        // Check if any count is non-zero
        for (int i = 0; i < 256; i++) {
            if (freqTable[i] != 0) {
                return false;
            }
        }
        
        return true; // Strings are anagrams
    }
};

2. Reverse Only Letters

Problem Statement

Given a string s, reverse only the English letters in the string while keeping all non-letter characters in their original positions.