valid-anagram-1755163786

Valid Anagram

Given two strings s and t, determine if t is an anagram of s. An anagram is a word formed by rearranging the letters of another word using all original letters exactly once (e.g., “listen” and “silent”).

The most efficient approach uses frequency counting with a hash map, similar to techniques employed in Two Sum and Longest Substring Without Repeating Characters.

Hash Map 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;
  }
};

Optimized Single-Pass Solution

Rather than using two hash maps, we can optimize with a single frequency array:

• Increment counts for characters in s
• Decrement counts for characters in t
• If all counts are zero at the end, t is an anagram of s

For lowercase English letters, a fixed-size array of 26 elements is more space-efficient than a hash map and provides $O(1)$ access.

 
#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