Solution For Valid Anagram

Problem Statement:

Given two strings s and t, return true if t is an anagram of s, and false otherwise.

Example 1:
Input: s = “anagram”, t = “nagaram”
Output: true

Example 2:
Input: s = “rat”, t = “car”
Output: false

Solution:

The approach here is to count the occurrence of each character in both the strings and compare them. If the count of the occurrences of every character in both strings is the same, then the second string is an anagram of the first string.

Algorithm:

1. If the lengths of the two strings are not equal, return false as they cannot be anagrams then.
2. Initialize an array of size 26 to represent the occurrences of each character in the strings using the ASCII value of each character.
3. Traverse the first string, and for each character increment the array value at the corresponding index.
4. Traverse the second string, and for each character decrement the array value at the corresponding index.
5. Finally, traverse the character array, if for any index the value is non-zero, then the second string is not an anagram of the first string.

Code:

class Solution:
def isAnagram(self, s: str, t: str) -> bool:

    if len(s) != len(t):
        return False

    occurrences = [0] * 26

    for char in s:
        occurrences[ord(char) - ord('a')] += 1

    for char in t:
        occurrences[ord(char) - ord('a')] -= 1

    for val in occurrences:
        if val != 0:
            return False

    return True

Time Complexity: O(n) – As we traverse both the strings only once.

Space Complexity: O(1) – We are using only an array of constant size which is 26.

Step by Step Implementation For Valid Anagram

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

def isAnagram(s, t):
        # Sort both strings
        s_sorted = "".join(sorted(s))
        t_sorted = "".join(sorted(t))
        
        # Compare sorted strings
        return s_sorted == t_sorted

var isAnagram = function(s, t) {
    //if the lengths of the two input strings are not the same, they cannot be anagrams
    if (s.length !== t.length) {
        return false;
    }
    
    //create two objects to store the counts of each character in the input strings
    let sCharCounts = {};
    let tCharCounts = {};
    
    //iterate through the first string and store the counts of each character in the first object
    for (let i = 0; i < s.length; i++) {
        let currentChar = s[i];
        if (sCharCounts[currentChar]) {
            sCharCounts[currentChar]++;
        } else {
            sCharCounts[currentChar] = 1;
        }
    }
    
    //iterate through the second string and store the counts of each character in the second object
    for (let i = 0; i < t.length; i++) {
        let currentChar = t[i];
        if (tCharCounts[currentChar]) {
            tCharCounts[currentChar]++;
        } else {
            tCharCounts[currentChar] = 1;
        }
    }
    
    //compare the two objects - if they have the same key/value pairs, the input strings are anagrams
    for (let key in sCharCounts) {
        if (!(key in tCharCounts)) {
            return false;
        }
        if (tCharCounts[key] !== sCharCounts[key]) {
            return false;
        }
    }
    
    return true;
};

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

public bool IsAnagram(string s, string t) 
{ 
    // If the two strings are not of equal length, 
    // then they cannot be anagrams 
    if (s.Length != t.Length) 
    { 
        return false; 
    } 
  
    // Sort both the strings 
    Array.Sort(s.ToCharArray()); 
    Array.Sort(t.ToCharArray()); 
  
    // Compare the sorted strings 
    for (int i = 0; i < s.Length; i++) 
    { 
        if (s[i] != t[i]) 
        { 
            return false; 
        } 
    } 
  
    return true; 
}