Valid Anagram - Leetcode Solution

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.

1