Valid Anagram

---

Valid Anagram: 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.

Example 1:

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

---

Example 2:

Input: s = "rat", t = "car"
Output: false

---

Constraints:

• 1 <= s.length, t.length <= 5 * 10^4
• s and t consist of lowercase English letters.

---

Try this Problem on your own or check similar problems:

1. Find Resultant Array After Removing Anagrams
2. Group Anagrams

Solution:

Java

public boolean isAnagram(String s, String t) {
  if(s.length() != t.length()) return false;
  int[] freqMap = new int[26];

  for(int i = 0; i < s.length(); ++i){
      char sChar = s.charAt(i);
      char tChar = t.charAt(i);
      ++freqMap[sChar-'a'];
      --freqMap[tChar-'a'];
  }

  for(int i = 0; i < 26; ++i){
      if(freqMap[i] != 0) return false;
  }

  return true;
}

JavaScript

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isAnagram = function (s, t) {
  if (s.length !== t.length) return false;
  let freqMap = new Array(26).fill(0);

  for (let i = 0; i < s.length; ++i) {
    let sChar = s.charAt(i);
    let tChar = t.charAt(i);
    ++freqMap[sChar.charCodeAt() - 97];
    --freqMap[tChar.charCodeAt() - 97];
  }

  for (let i = 0; i < 26; ++i) {
    if (freqMap[i] !== 0) return false;
  }

  return true;
};

Python

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False
        freqMap = [0] * 26

        for i in range(len(s)):
            sChar = s[i]
            tChar = t[i]
            freqMap[ord(sChar) - 97] += 1
            freqMap[ord(tChar) - 97] -= 1

        for count in freqMap:
            if count != 0:
                return False

        return True

C++

class Solution {
public:
    bool isAnagram(string s, string t) {
        if (s.length() != t.length()) return false;
        vector<int> freqMap(26, 0);

        for (int i = 0; i < s.length(); ++i) {
            char sChar = s[i];
            char tChar = t[i];
            ++freqMap[sChar - 'a'];
            --freqMap[tChar - 'a'];
        }

        for (int count : freqMap) {
            if (count != 0) return false;
        }

        return true;
    }
};

---

Time/Space Complexity:

• Time Complexity: O(n)
• Space Complexity: O(1)

---

Explanation:

Since both strings have to be of the same length we can be sure we will traverse n characters where n is length either one of our input strings leading to linear time complexity. Since we're only handling lowercase letter we can create an array containing 26 elements leading to constant space complexity, than we would use mapping c - 'a' (where c is a lowercase letter, e.g. c = 'a', than it would map to 0, if it's b it will map to 1 and so on). We iterate over strings, incrementing the freqMap for a character in string s and decrementing it for a character t, doing it this way we can be sure if there are same mathing letters in both strings the total count will be 0 (you increment for one string, and decrement for the other). So our final check is to iterate over freqMap and see if there is any non-zero element which makes the strings not anagrams. We return false if there is, otherwise we return true indicating valid anagrams.