242. Valid Anagram#

Difficulty: Easy

Link to Problem: To see the Valid Anagram problem on LeetCode, click here!

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.

Constraints:

  • 1 <= s.length, t.length <= \(5 * 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?

Solution:#

Here’s a Python function to solve this problem:

def isAnagram(s: str, t: str) -> bool:
    # Check if the lengths of s and t are not equal
    if len(s) != len(t):
        return False

    # Create dictionaries to store character frequencies for s and t
    countS, countT = {}, {}

    # Count character frequencies in s
    for i in range(len(s)):
        countS[s[i]] = 1 + countS.get(s[i], 0)

    # Count character frequencies in t
    for i in range(len(t)):
        countT[t[i]] = 1 + countT.get(t[i], 0)

    # Check if the character frequencies in s and t are the same
    return countS == countT

Explanation:#

  1. The code defines a class called Solution with a method isAnagram that takes two input strings, s and t, and returns a boolean (True or False) based on whether t is an anagram of s.

  2. The first check performed in the method is whether the lengths of s and t are equal. If they are not equal, it immediately returns False because strings of different lengths cannot be anagrams of each other.

  3. Two dictionaries, countS and countT, are created to store the frequency of characters in s and t, respectively. These dictionaries will be used to count the occurrences of each character in the strings.

  4. The code then enters a loop to iterate through each character in string s using a for loop. Inside the loop, it updates the countS dictionary. The line countS[s[i]] = 1 + countS.get(s[i], 0) increments the count of character s[i] in countS by 1. If the character is not already in the dictionary, it initializes the count to 1.

  5. Similarly, the code iterates through each character in string t and updates the countT dictionary in the same way.

  6. After counting the character frequencies in both strings, the code compares the two dictionaries using countS == countT. If the dictionaries are equal, it means that both strings have the same character frequencies, and therefore, t is an anagram of s. In this case, the method returns True.

  7. If the dictionaries are not equal, the method returns False, indicating that t is not an anagram of s.

In summary, this code efficiently determines whether two input strings are anagrams by counting the character frequencies in each string using dictionaries and then comparing these counts. If the character frequencies match, the strings are considered anagrams, and the method returns True; otherwise, it returns False.

Test cases#

# Example 1:
s = "anagram"
t = "nagaram"
print(isAnagram(s, t))

True

# Example 2
s = "rat"
t = "car"
print(isAnagram(s, t))

False

Time and Space Complexity Analysis#

Let’s analyze the time and space complexity of the provided code:

Time Complexity:

  1. The code first checks whether the lengths of the input strings s and t are equal, which takes constant time. This check has a time complexity of O(1).

  2. The code then iterates through both strings, s and t, once to count the character frequencies. Since both strings have a maximum length of 5 * 10^4, the worst-case scenario is that the code iterates through 5 * 10^4 characters in each string. This results in a linear time complexity of O(n), where n is the length of the longer of the two input strings (s or t).

  3. Finally, the code compares the two dictionaries countS and countT to check if the character frequencies match. This comparison takes O(n) time in the worst case, where n is the length of the longer string.

Overall, the time complexity of the code is O(n), where n is the length of the longer input string.

Space Complexity:

  1. The code uses two dictionaries, countS and countT, to store the character frequencies of the input strings s and t. In the worst case, both dictionaries can contain all unique characters from the input strings. Since the input strings can have a maximum length of 5 * 10^4, the space complexity for these dictionaries is O(5 * 10^4) or simply O(n), where n is the length of the longer input string.

  2. The code uses a few additional variables for bookkeeping, but these variables have constant space requirements and do not depend on the input size. Therefore, they do not significantly impact the overall space complexity.

In summary, the space complexity of the code is O(n), where n is the length of the longer input string.

Challenging Exercises:#

  1. Anagram Chains: Given a list of words, find the longest chain of anagrams, where each word in the chain is an anagram of the previous word. For example, given [“bat”, “tab”, “cat”, “tac”, “dog”], the longest anagram chain is [“bat”, “tab”, “cat”, “tac”].

  2. Minimum Deletions to Make Anagrams: Given two strings s and t, find the minimum number of character deletions required in both strings to make them anagrams of each other. For example, if s = "hello" and t = "billion", you can remove the characters “heo” from s and “billi” from t to make them anagrams (“lo” and “on” are left in the two strings).