Given two strings s and t, determine if t is an anagram of s.

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.

Constraints

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

Example

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

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

Solution

Approach 1: Frequency Counting

One efficient way to check if two strings are anagrams is to count the frequency of each character in both strings. If the frequency counts for every character are identical, then the strings are anagrams.

  • Initial Check: First, check if the lengths of s and t are different. If they are, they cannot be anagrams, so return false.
  • Initialize Counter: Create a frequency map (or an array of size 26 for lowercase English letters) to store character counts.
  • Populate Counts for s: Iterate through string s. For each character, increment its count in the frequency map.
  • Adjust Counts for t: Iterate through string t. For each character, decrement its count in the frequency map.
  • Verify Counts: After processing both strings, iterate through the frequency map. If all counts are 0, it means every character in s had a corresponding character in t (and vice-versa) and they are anagrams. If any count is not 0, they are not anagrams.

Approach 2: Sorting (Alternative)

An alternative, though often less efficient for very long strings, is to sort both strings. If the sorted versions of s and t are identical, then they are anagrams.

  • Initial Check: As before, check if lengths differ.
  • Sort Strings: Convert both strings to character arrays, sort them alphabetically.
  • Compare Sorted Strings: Convert the sorted character arrays back to strings and compare them. If they are equal, return true.

Python Implementation (Frequency Counting)

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False

        # Using a dictionary for frequency counts
        # Can also use an array of 26 integers: counts = [0] * 26
        char_counts = {}
        
        # Increment counts for characters in s
        for char in s:
            char_counts[char] = char_counts.get(char, 0) + 1
            
        # Decrement counts for characters in t
        for char in t:
            char_counts[char] = char_counts.get(char, 0) - 1

        # Check if all counts are zero
        for count in char_counts.values():
            if count != 0:
                return False
                
        return True