Anagram

Given two strings s1 and s2 consisting of lowercase characters. The task is to check whether two given strings are an anagram of each other or not. An anagram of a string is another string that contains the same characters, only the order of characters can be different. For example, act and tac are an anagram of each other. Strings s1 and s2can only contain lowercase alphabets.

Note: You can assume both the strings s1 & s2 are non-empty.

Examples :

Input: s1 = "geeks", s2 = "kseeg"
Output: true
Explanation: Both the string have same characters with same frequency. So, they are anagrams.

Input: s1 = "allergy", s2 = "allergic"
Output: false
Explanation: Characters in both the strings are not same, so they are not anagrams.

Input: s1 = "g", s2 = "g"
Output: true
Explanation: Character in both the strings are same, so they are anagrams.

Constraints:
1 ≤ s1.size(), s2.size() ≤ 10⁵

Approach 01:

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

class Solution {
public:
    bool areAnagrams(const string& str1, const string& str2) {
        // Check if lengths are different
        if (str1.length() != str2.length()) {
            return false;
        }

        // Count frequencies of characters in both strings
        unordered_map<char, int> frequencyStr1, frequencyStr2;
        for (char ch : str1) {
            frequencyStr1[ch]++;
        }
        for (char ch : str2) {
            frequencyStr2[ch]++;
        }

        // Compare frequencies
        for (const auto& entry : frequencyStr1) {
            char character = entry.first;
            int count = entry.second;
            if (frequencyStr2[character] != count) {
                return false;
            }
        }
        return true;
    }
};

import collections

class Solution:
    def areAnagrams(self, str1, str2):
        # Check if lengths are different
        if len(str1) != len(str2):
            return False

        # Count frequencies of characters in both strings
        frequencyStr1 = collections.Counter(str1)
        frequencyStr2 = collections.Counter(str2)

        # Compare frequencies
        for char, count in frequencyStr1.items():
            if frequencyStr2[char] != count:
                return False
        return True

Time Complexity

• Length check:

  Checking if the lengths of the two strings are equal takes \(O(1)\), as it involves comparing integer values.

• Frequency calculation:

  Iterating through each character of str1 and str2 to populate the frequency maps takes \(O(n)\), where \(n\) is the length of the strings. This step is performed twice, but it still results in \(O(n)\) overall for this part.

• Frequency comparison:

  Iterating through the frequencyStr1 map to compare frequencies with frequencyStr2 takes \(O(n)\) in the worst case, as each character is checked once.

• Overall Time Complexity:

  The overall time complexity is \(O(n)\), where \(n\) is the length of the strings.

Space Complexity

• Frequency maps:

  Two unordered maps frequencyStr1 and frequencyStr2 are used to store character frequencies. Each map can have up to \(O(k)\) entries, where \(k\) is the size of the character set (e.g., 26 for lowercase English letters or 256 for extended ASCII). This results in \(O(k)\) space for each map, and \(O(k)\) overall since \(k \leq n\).

• Overall Space Complexity:

  The overall space complexity is \(O(k)\), where \(k\) is the size of the character set.