Valid Anagram LeetCode Problem 242 [Python Solution]

In this blog post, we’ll solve Valid Anagram LeetCode Problem 242 which goal is to determine if two given strings, s and t, are anagrams of each other.

The Question

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

Problem Overview

To solve this problem, we will explore a few different approaches.

First, we’ll outline a straightforward solution using hash maps to count the occurrences of each character in both strings and then compare the counts.

Next, we’ll optimize this solution to use less memory.

Finally, we’ll introduce a solution that leverages sorting to determine if the strings are anagrams.

Understanding the Constraints

Before diving into the solutions, it’s essential to understand the constraints of the problem:

The length of strings s and t can range from 1 to 50,000 characters.
Both s and t consist of lowercase English letters.

Now, let’s explore the solutions in detail.

Tackling Valid Anagram LeetCode Problem with Bruteforce Approach

The most straightforward approach is to count the occurrences of each character in both strings s and t using hash maps.

We’ll create two hash maps, one for each string, with characters as keys and their respective counts as values.

Then, we’ll compare the two hash maps to check if they have the same counts for each character.

Here’s the Python code for this approach:

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

    # Create hash maps to count character occurrences in both strings
    count_s, count_t = {}, {}

    # Count occurrences in string s
    for index in range(len(s)):
        count_s[s[index]] = 1 + count_s.get(s[index], 0)

    # Count occurrences in string t
    for index in range(len(t)):
        count_t[t[index]] = 1 + count_t.get(t[index], 0)

    # Compare the two hash maps
    return count_s == count_t

The time complexity of this approach is O(s + t), where s and t are the lengths of the input strings.

The space complexity is also O(s + t) because we create two hash maps to store the character counts.

Efficient Approach with Hash Map

While the brute force approach works, solving the valid anagram LeetCode problem this way consumes extra memory due to the use of two hash maps.

We can optimize this by using only one hash map to count characters in one string while decrementing the counts based on the characters in the other string.

If both strings are anagrams, the hash map will be empty after processing.

Here’s the Python code for the optimized solution:

Valid Anagram Solution with Hash Map in Python

View on GitHub ➹

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

    # Create a hash map to count character occurrences in string s
    count_s = {}

    # Count occurrences in string s
    for char in s:
        count_s[char] = 1 + count_s.get(char, 0)

    # Decrement counts based on characters in string t
    for char in t:
        if char not in count_s:
            return False
        count_s[char] -= 1
        if count_s[char] == 0:
            del count_s[char]

    # If the hash map is empty, the strings are anagrams
    return not count_s

This optimized solution has the same time complexity as O(s + t) but consumes less memory as it uses only one hash map.

Efficient Approach with Sorting

Another approach to check if two strings are anagrams is by sorting both strings and comparing them.

If the sorted strings are equal, the original strings are anagrams.

Here’s the Python code for this approach:

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

    # Sort both strings and compare them
    return sorted(s) == sorted(t)

While this solution is simple, it has a time complexity of O(n log n) due to the sorting step, where n is the length of the input strings.

The space complexity is O(1) because it doesn’t use extra memory for hash maps.

Reasoning Behind Our Efficient Approaches

In the optimized approach using a hash map, we leverage the fact that if two strings are anagrams, they must have the same set of characters with the same counts, albeit in a different order.

By iterating through both strings and updating the counts in a single hash map, we can efficiently determine if they are anagrams.

If the hash map is empty after processing both strings, it indicates that all characters canceled each other out, confirming that the strings are anagrams.

The sorting approach is straightforward but less efficient due to the sorting step.

However, it has a space complexity of O(1) since it doesn’t require additional memory.

Conclusion

In this blog post, we explored different approaches to solving the “Valid Anagram” problem on LeetCode.

We started with a brute-force approach using hash maps to count character occurrences in both strings.

We then optimized this solution to use less memory by employing a single hash map.

Finally, we introduced a sorting-based approach to determine if two strings are anagrams.

While all three approaches are valid, the efficient approach with a hash map strikes a balance between time complexity and memory usage.

Depending on the specific requirements of your problem and the available resources, you can choose the most suitable solution.

Solve the Valid Anagram on LeetCode today.

If you have any questions, or suggestions, or want to share your thoughts, please feel free to leave a comment below.

Happy coding!