Valid Anagram Leetcode Solution

Problem Statement

Valid Anagram Leetcode Solution – 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

Constraints:

Follow up: What if the inputs contain Unicode characters? How would you adapt your solution to such a case?

Approach

Idea:

1. if two strings are anagrams then the frequency of every char in both of the strings are same.
2. we count the freq of every character in string1 and string 2.
3. here to count freq we make an array of size 26.
4. characters in the string are from ‘a’ to ‘z’ so we can represent ‘a’ as 0 and ‘z’ as 25 by doing (int idx=ch-‘a’)
5. now we compare freq1[i] and freq2[i] for every index i from 0 to 26 and if they are different we return false
6. otherwise, we return true

C++ Program of  Valid Anagram

class Solution {
public:
    bool isAnagram(string s, string t) {
       
        if(s.length()!=t.length())return false;
        
        vector<int> freq1(26,0),freq2(26,0);
        
        for(int i=0;i<s.length();i++)
        {
            freq1[s[i]-'a']++;
            freq2[t[i]-'a']++;
        }
        
        for(int i=0;i<26;i++)
        {
            if(freq1[i]!=freq2[i])return false;
        }
        
        return true;
        
    }
};

JAVA Program of  Valid Anagram

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

Time Complexity for Valid Anagram Leetcode Solution

O(n) +O(26) i.e=> O(n) as we iterate the string to count the frequency of every character where n is the length of the string.

Space Complexity

O(26) i.e => O(1) as we are using  26 size-frequency array to store the frequency of every character.