Problem Informations

• Problem Index: 242
• Problem Link: Valid Anagram
• Topics: Hash Table, String, Sorting

Problem Description

Given two strings s and t, return true if t is an anagram of s, and false otherwise.

Example 1:

Input: s = “anagram”, t = “nagaram”

Output: true

Example 2:

Input: s = “rat”, t = “car”

Output: false

Constraints:

• $1 \leq s.length, t.length \leq 5 \times 10^4$
• s and t consist of lowercase English letters.

Follow up: What if the inputs contain Unicode characters? How would you adapt your solution to such a case?

Intuition

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. The problem involves determining if one string is an anagram of another. The primary observation is that two strings are anagrams if the frequency of each letter in one string matches the frequency of each letter in the other string. Given that the strings consist of lowercase English letters, we can utilize an array to count these frequencies efficiently.

Approach

To solve this problem, we utilize an array of fixed size (26) to account for each lowercase English letter. The array is initialized with zeros, corresponding to the alphabets ‘a’ to ‘z’. The algorithm proceeds with the following steps:

1. Frequency Count of First String:

   • Traverse through string s and increment the corresponding index in the letter_count array for each character. Specifically, for a character ch in s, update the array at index ch - 'a' to reflect the incremented count.

2. Frequency Count Adjustment for Second String:

   • Traverse through string t and decrement the corresponding index in the letter_count array for each character. Again, for a character ch in t, update the array at index ch - 'a' to reflect the decremented count.

3. Verification of Anagram Status:

   • After processing both strings, examine the letter_count array. If all counts are zero, this indicates that both strings have identical character frequencies, confirming that t is an anagram of s. If any count is not zero, this suggests a discrepancy in character frequencies, meaning t is not an anagram of s.

By using this technique, we efficiently determine whether two strings are anagrams by comparing the character frequency maps. The complexity of this method is linear, $O(n)$, where $n$ is the length of the strings (assuming both strings are of the same length), making it well-suited for the given problem constraints.

Code

C++

class Solution {
public:
    bool isAnagram(string s, string t) {
        // Array to count the frequency of each letter in the English alphabet
        int letter_count[26] = {0};

        // Increment the count for each character in the first string
        for (char ch : s) {
            letter_count[ch - 'a']++;
        }

        // Decrement the count for each character in the second string
        for (char ch : t) {
            letter_count[ch - 'a']--;
        }

        // Check if all counts are zero, which means they are anagrams
        for (int count : letter_count) {
            if (count != 0) {
                return false; // Not an anagram if any count is non-zero
            }
        }
        
        return true; // True if all counts are zero, meaning t is an anagram of s
    }
};

Python

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        # Array to count the frequency of each letter in the English alphabet
        letter_count = [0] * 26

        # Increment the count for each character in the first string
        for ch in s:
            letter_count[ord(ch) - ord('a')] += 1

        # Decrement the count for each character in the second string
        for ch in t:
            letter_count[ord(ch) - ord('a')] -= 1

        # Check if all counts are zero, which means they are anagrams
        for count in letter_count:
            if count != 0:
                return False  # Not an anagram if any count is non-zero
        
        return True  # True if all counts are zero, meaning t is an anagram of s

Complexity

• Time complexity: The time complexity of this algorithm is $O(n + m)$, where $n$ is the length of string $s$ and $m$ is the length of string $t$. This is because the algorithm traverses each character of both strings exactly once to count and adjust the frequencies in the letter_count array.

• Space complexity: The space complexity is $O(1)$, as the algorithm uses a fixed-size array of 26 integers to store the character frequencies of the English alphabet. This space does not scale with the input size, as it only depends on the fixed size of the alphabet.