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. You may assume the strings contain only lowercase English letters.

  • Constraints:

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

  • Example 1:

Input: s = "anagram", t = "nagaram"
Output: true
  • Example 2:
Input: s = "rat", t = "car"
Output: false

Solution

To determine if two strings are anagrams, we need to check if they contain the same characters with the same frequencies. Here's an efficient approach:

  • Check Lengths First: If the lengths of s and t are different, they cannot be anagrams. Return false immediately.
  • Character Frequency Array: Since the strings contain only lowercase English letters, we can use an array of size 26 (for 'a' through 'z') to store character counts.
    • Iterate through s: For each character, increment its corresponding count in the frequency array.
    • Iterate through t: For each character, decrement its corresponding count in the frequency array. If at any point a character's count becomes negative, it means t has more occurrences of that character than s, so they are not anagrams. Return false.
  • Final Check: If both loops complete without returning false, it implies all characters had matching frequencies. Return true.
class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        # Anagrams must have the same length
        if len(s) != len(t):
            return False

        # Create a frequency array for 26 lowercase English letters
        # Index 0 for 'a', 1 for 'b', ..., 25 for 'z'
        counts = [0] * 26

        # Increment counts for characters in string s
        for char_s in s:
            counts[ord(char_s) - ord('a')] += 1
        
        # Decrement counts for characters in string t
        for char_t in t:
            counts[ord(char_t) - ord('a')] -= 1
            # If a count becomes negative, it means t has an extra char
            # that wasn't in s, or more occurrences than s.
            if counts[ord(char_t) - ord('a')] < 0:
                return False
        
        # If we reach this point, it means all characters in t were found
        # in s with sufficient counts. Since lengths were equal, all counts
        # must now be zero, indicating they are anagrams.
        return True