242. Valid Anagram

Intuition

An anagram of a string is another string that contains the same characters, only the order of characters can be different.

Approach

1. Initial Check:

If the lengths of the two strings s and t are not equal, they cannot be anagrams, so return False.

1. Frequency Count: Use a frequency counter (hashmap) to count occurrences of each character in both strings.
2. Comparison: Compare the frequency counts of both strings. If they match, t is an anagram of s; otherwise, it is not.

Complexity

Time Complexity:

O(n), where n is the length of the strings s and t. This is because we iterate through each string once to build the frequency counters and then compare them.

Space Complexity:

O(1) extra space, since the frequency counter will have at most 26 entries (for each letter of the alphabet).

Code

C++

class Solution {
public:
    bool isAnagram(string s, string t) {
        string sortedS = sortString(s);
        string sortedT = sortString(t);
        
        return sortedS == sortedT;
    }
private:
    string sortString(string str) {
        sort(str.begin(), str.end());
        return str;
    }
};

Python

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        return self.sortString(s) == self.sortString(t)
    def sortString(self, str: str) -> str:
        return ''.join(sorted(str))

Java

class Solution {
    public boolean isAnagram(String s, String t) {
        return sortString(s).equals(sortString(t));
    }
    private String sortString(String str) {
        char[] charArray = str.toCharArray();
        Arrays.sort(charArray);
        return new String(charArray);
    }
}

JavaScript

var isAnagram = function(s, t) {
    let r1 = sortString(s);
    let r2 = sortString(t);
    if (r1 === r2) 
    return true;
    else 
    return false;
};
let sortString = (str) => {
    return [...str].sort((a, b) => 
    a.localeCompare(b)).join("");
}