242. Valid Anagram

Problem Link

Given strings s and t, they're Anagram if we can rearrange the characters of one to form another. This can be reworded as, both strings should have same characters. We can check this by storing the frequency of one string and match them with the other.

Pseudocode

• If strings have different number of characters, we can return early as they'll never have same characters.
• Otherwise, we'll iterate over one string and store the frequency of each character in a hashmap.
• Iterate over other string to reduce the frequency of encountered character.
• During which, we can say the strings aren’t anagrams if we encounter any character which either isn't present in our hashmap, or the frequency of character is exhausted.

Runtime Complexity

Time: \(O(n)\), since we're only iterating the strings twice, with insertion and querying hashmap being \(O(1)\) operation.

Space: \(O(n)\), due to the hashmap used for storing characters frequency.

PythonGo

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False

        freq = dict()
        for i in s:
            freq[i] = freq.get(i, 0) + 1

        for i in t:
            if i not in freq or freq[i] == 0:
                return False

            freq[i] -= 1

        return True

func isAnagram(s string, t string) bool {
    if len(s) != len(t) {
        return false
    }
    freq := make(map[rune]int)
    for _, ch := range s {
        freq[ch]++
    }
    for _, ch := range t {
        if val, ok := freq[ch]; !ok || val == 0 {
            return false
        }
        freq[ch]--
    }
    return true
}

---