242. Valid Anagram - LeetCode Fastest Solution

Hello Code Recipian! Welcome back to another article on LeetCode problem solutions. In our previous article we discussed the solution for LeetCode 112. Path Sum problem. Today we will be solving LeetCode problem 242. Valid Anagram.

Let's check out the problem statement.

Problem Statement: Valid Anagram

Given two strings s and t, return true if t is a valid anagram of s. Otherwise return false.

Note: An anagram is a word or phrase made by rearranging the letters of another word or phrase.

Example 1:

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

Output: true

Example 2:

Input: s = "listen", t = "silent"

Output: true

Example 3:

Input: s = "car", t = "bar"

Output: false

Constraints:

• 1 <= s.length, t.length <= 5 * 10^4

• s and t consist of lowercase English letters.

Solution

To ascertain if s and t are valid anagrams, we must check the following criteria:

1. Both s and t must have the same number of characters (length of s must be equal to t).

2. The frequency (count) of characters in s must be the same as that in t.

We can utilize the hashmap data structure to solve this problem efficiently in linear time. The idea is to use the hashmap to count the characters in s and t and based on this count we determine the final result.

Let's see how this algorithm works in detail.

Algorithm

Below is a step-by-step explanation for the working of the algorithm:

1. Preliminary Validation:

   Before verifying anything else, the initial step is to confirm whether the strings s and t have the same length. If the lengths of s and t are not equal, they can never be anagrams of each other. Therefore, if they are not equal we straight away return false as result.

   
   

2. Initialization: If the lengths are equal, we initialize a hashmap, let's call it freqMap. freqMap is used to maintain the count characters in s and t. It takes a character key and integer value. Initially this map is empty.

   
   

3. Count characters in s: The first step is to iterate through the given string s and count its characters. We iterate through each character in s one-by-one and in each iteration we increment the count for that character in freqMap.

   
   

4. Decrement freqMap count: Next, we iterate through string t. In each iteration we decrement the current character count from freqMap. The logic behind this is that, if s and t are anagrams then the count of characters in s should match the character count in t. So, when we decrement character count for string t, every character count from s in freqMap should become 0.
   

5. Check if every character count is zero:

   Now we iterate through the freqMap. In each iteration we check the current character count in freqMap:

   1. If the current character count is zero, continue iterating.

   2. At any point if we find that the current character count is not zero, then s and t are not anagrams. Therefore, we immediately return false as result.

      
      

6. Return true as result:

   If the execution comes out of the 3rd loop in step 5, it means every character in freqMap is equal to 0 and s and t are anagrams. Therefore, we return result as true.

Note: We can also solve this problem using sorting approach, but the time complexity for the sorting solution would be O(n log n).

Simulation

Below is a pictorial depiction for the working of the algorithm:

Want to master coding? Looking to upskill and crack interviews? We suggest you check out these specially designed courses:

1. Udemy Video Tutorials - Available at 95% off

2. System Design Interview Complete Guide

3. Cracking The Coding Interview - Most Preferred Book For Coding Interviews

4. Data Structures And Algorithms - A Complete Guide 

5. Learn In-Demand Tech Skills And Stay Ahead Of Others

Code

Go Solution

Python Solution

Java Solution

JavaScript Solution

TypeScript Solution

C++ Solution

C# Solution

C Solution

PHP Solution

Kotlin Solution

Swift Solution

Ruby Solution

Scala Solution

Rust Solution

Complexity Analysis

Time Complexity

Length Check:

Length check is a constant time operation, hence the time complexity is O(1).

First Loop:

At this point, length of both s and t are equal (due to length check in step 1). If n is the length of s and t, time complexity of the first loop is O(n), since we are iterating through every element in s to count its characters.

Second Loop:

Similarly, the time complexity of the second loop is also O(n) as we iterate through every character in t.

Third Loop:

This loop, in the worst case can make upto 26 iterations. This because the input consists of only lowercase English letters (as per problem constraint) making time complexity for this loop O(1).

Therefore, the overall time complexity of this solution is O(1) + O(n) + O(n) + O(1) = O(n).

Space Complexity

This algorithm uses hashmap freqMap to store the count of letters in s and t. However, since the input consists of only lowercase English letters, freqMap can have at most 26 elements. Apart from this we are not using any extra variables that have impact on the space complexity.

Therefore, the space complexity of this solution is O(1).

That brings us to the end of this article. We appreciate the time you have taken to read through it. If you have any questions, feel free to ask them in the comments below. We're here to help and will gladly answer your queries.

If you enjoyed this article, please subscribe to our website and Youtube channel. Your support inspires us to bring out more such articles in future.

Don't forget to delve into more such fascinating articles from Code Recipe in our blogs section. There's a wealth of knowledge waiting for you there!

Code Recipe Limited Time Offer: Get 100% discount on Code Recipe Membership Plan. Join now and get exclusive access to premium content for free. Hurry! Offer only available for a limited time - Join now.

Follow us: YouTube, Facebook, Twitter, LinkedIn, Tumblr, Instagram.