# 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/

## 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;

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.