Valid Anagram Solution - LeetCode 242

Photo by Chris Ried on Unsplash

Valid Anagram Solution - LeetCode 242

Intuition

After seeing the problem statement, I thought of the best one HashMap :)
To store the frequency of one string and compare that with another string's frequency. However, we can also minimize the extra computation of importing and implementing a hashmap by using an array.

Approach

We know that the characters are English lowercase letters only. Therefore we make an array of lengths 26 to store the frequency. A total of 26 letters are there.
Now we know that anagram means having the same frequency of each and every letter and their difference is the permutation of those letters.

For example

s = 'abc'
b = 'cba'

both having the same frequency of each letter but their permutation is different in both the string.

So my approach is simple. First, by iterating one string, we will store the frequency of each letter in the array.
We got :

alphas = [1,1,1,0,0,0,0,.....,0]; # total length 26

now, we have the same frequency of letters in both the string.
By iterating another string we will decrement the frequency.
we got :

alphas = [0,0,0,0,0,0,0,......,0] # total length 26

Now if both are anagrams, we must get the elements of the array to 0 in the because the same frequency of letters exists in both strings.

So now we iterate through the array and check if the element equals 0 then return true. Otherwise, return false.

Note : ch-'a' gives the index because if ch == 'b', then 'b' - 'a' = 1 which we will consider as the index of 'b'.

Complexity

  • Time complexity: O(n)
  • Space complexity:O(1)

It is constant because we use a constant size of the array (26).

Code

class Solution {
    public boolean isAnagram(String s, String t) {
        int alphas[] = new int[26];
        for(char ch : s.toCharArray()){
            alphas[ch-'a']++;
        }
        for(char ch : t.toCharArray()){
            alphas[ch-'a']--;
        }
        for(int i : alphas){
            if(i != 0){
                return false;
            }
        }
        return true;
    }
}

I hope you understood. If not, do comment.

Thank You

Problem: https://leetcode.com/problems/valid-anagram/description/

My LeetCode Profile: https://leetcode.com/5p7Ro0t/