valid-anagram-1755163786

Valid Anagram

Given two strings s and t, write a function to determine if t is an anagram of s. The most efficient solution is using a hash map to count the frequency of each character in both strings and then compare the counts.

Solution

 
#include <string>
#include <unordered_map>
using namespace std;
 
class Solution {
public:
  bool isAnagram(string s, string t) {
    // string can't be an anagram if it is of a different size
    if (s.size() != t.size())
      return false;
    unordered_map<char, unsigned int> hashMap;
    unordered_map<char, unsigned int> hashMap2;
 
    for (int i = 0; i < s.size(); ++i) {
      hashMap[s[i]] += 1;
      hashMap2[t[i]] += 1;
    }
    return hashMap == hashMap2;
  }
};

Optimization

The above solution uses two hash maps to count the frequency of characters in both strings. However, we can optimize it to use a single hash map by incrementing the count for characters in s and decrementing for characters in t. If all counts are zero at the end, then t is an anagram of s. Instead of storing this data in a hash map, we can use a vector of size 26 (for each letter in the alphabet) to count the frequency of characters, which is more space-efficient.

 
#include <string>
#include <vector>
using namespace std;
 
class Solution {
public:
  bool isAnagram(string s, string t) {
    // string can't be an anagram if it is of a different size
    if (s.size() != t.size())
      return false;
 
    vector<int> hashMap(26, 0);
    for (int i = 0; i < s.size(); ++i) {
      hashMap[s[i] - 'a'] += 1;
      hashMap[t[i] - 'a'] -= 1;
    }
    for (int i = 0; i < 26; i++) {
      if (hashMap[i] != 0)
        return false;
    }
    return true;
  }
};

The above solution can be further optimised for memory by using an int array instead of a vector, as the size is fixed and known at compile time.

int hashMap[26] = {0}; // Initialize an array of size 26 to zero