Data Structures & Algorithms in Java – Strings – Valid Anagram

Problem:

Given two strings , check if they are valid anagrams of each other.

For example,

“anagram” is an anagram of “nagaram”.

So return true

“cat” is not an anagram of “dog” so return false.

Assumptions:

• All the letters are lowercase English letters.

Try out the solution here:

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

Solution:

Hint:

Keep a count of each character in the words and compare them against each other.

ALGORITHM:

STEP 1: Check if both the strings are of equal length, else return false

STEP 2: Initialize an array of length 26 to represent each small case English alphabet

STEP 3: For each character in the first word , increment the count of the character

STEP 3b: For each character in the second word , decrement the count of the character from the count array.

STEP 4: Check if there is a non zero value in the array , if so return false

Code:

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

We perform a subtraction operation “c-‘a’” inside the for loop because the character a is represented by the integer value 65 , subtracting it would let us store the alphabet count starting from the index 0 in the count array (a = 0, b = 1 , c=2 ..). This allows us to declare the count array size to be 26.

Time complexity of the above algorithm is O(m + n ) where m represents the first string length and n represents the second string length

Instead of an integer array we could also use a map to store the character count , this would be better if the characters include upper case letters and other unicode characters. But it would be slower due to the hashmap put, get and cointainsKey operations.