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.

Examples

Example 1

Input : s = "anagram" , t = "nagaram"
Output : true

Explanation : We can rearrange the characters of string s to get string t as frequency of all characters from both strings is same.

Example 2

Input : s = "dog" , t = "cat"
Output : false

Explanation : We cannot rearrange the characters of string s to get string t as frequency of all characters from both strings is not same.

Example 3

Input : s = "eat" , t = "tea"
Output :
true

Constraints

• 1 <= s.length , t.length <= 5*104
• s and t consist of only lowercase English letters

Approaches

1️⃣ Sorting

Intuition:

The letters of an anagram should form identically sequences if alphabetically sorted. By furthering this thought process a method to check for anagrams would be sorting both strings. By sorting both strings and then comparing them, we can easily determine if they contain the same characters in the same frequencies.

Approach:

1. Sort the characters of both strings using an inbuilt sort function, so that if they are anagrams, the sorted strings will be identical.
2. Compare the sorted versions of both strings. If they match, the original strings are anagrams; otherwise, they are not.
3. Return true if the sorted strings are identical, otherwise return false.

Code:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    bool anagramStrings(string& s, string t) {
        // If lengths are not equal, they cannot be anagrams
        if (s.length() != t.length()) return false;

        // Sort both strings
        sort(s.begin(), s.end());
        sort(t.begin(), t.end());

        // Compare sorted strings
        return s == t;
    }
};

int main() {
    Solution solution;
    string str1 = "INTEGER";
    string str2 = "TEGERNI";
    bool result = solution.anagramStrings(str1, str2);
    cout << (result ? "True" : "False") << endl;
    return 0;
}

Complexity Analysis:

• Time Complexity:O(N log N) due to sorting each string.
• Space Complexity:O(1) as no additional data structures are used.

2️⃣ Hash Map (Frequency Count)

Instead of sorting, we can use a hash map (or array) to count the frequency of each character in both strings and then compare these counts.

Steps:

• Check if the lengths of s and t are equal. If not, they can't be anagrams.
• Create a frequency count array (or hash map) for the characters in s.
• Decrease the frequency count for the characters in t.
• If all frequencies are zero, then t is an anagram of s.

Code:

#include <string>
#include <iostream>
using namespace std;

bool anagramStrings(const string& s, const string& t) {
    if (s.size() != t.size()) return false;

    int frequency[26] = {0};

    // Combine counting for s and t into one loop
    for (int i = 0; i < s.size(); i++) {
        frequency[s[i] - 'a']++;  // Increment for s
        frequency[t[i] - 'a']--;  // Decrement for t
    }

    // Check if all frequencies are zero
    for (int i = 0; i < 26; i++) {
        if (frequency[i] != 0) {
            return false;
        }
    }

    return true;
}

int main() {
    string s = "listen";
    string t = "silent";

    if (anagramStrings(s, t)) {
        cout << t << " is an anagram of " << s << endl;
    } else {
        cout << t << " is not an anagram of " << s << endl;
    }

    return 0;
}

Complexity Analysis:

• Time Complexity: O(n), where n is the length of the strings (as we only need to traverse the strings once).
• Space Complexity: O(1), since the size of the alphabet (for English letters, it's 26) is constant.