242. Valid Anagram

INFO

Problem: Valid Anagram

Pattern: Character frequency counting

Two strings are anagrams when they contain the same characters with the same counts, even if the order is different. Sorting both strings is possible, but counting characters gives a direct linear solution.

Approach

1. Count each character in the first string.
2. Count each character in the second string.
3. If the dictionaries have different numbers of keys, return false.
4. For every character in the first dictionary, compare its count with the second dictionary.
5. Return true only when every count matches.

This checks both membership and frequency. For example, "aab" and "abb" use the same number of characters, but the counts differ.

Swift Notes

The solution uses [Character: Int] dictionaries. For each character, it either increments the existing count or starts the count at 1.

Swift's dictionary subscript returns an optional, so the code uses if let count = sLetterCount[i] to safely update existing values.

Complexity

• Time complexity: O(n), where n is the length of the strings.
• Space complexity: O(k), where k is the number of distinct characters.

Edge Cases

• Different string lengths cannot be anagrams.
• Repeated characters must have matching counts.
• The logic works for Swift Character values, not only ASCII letters.

class Solution {
    func isAnagram(_ s: String, _ t: String) -> Bool {
        var sLetterCount: [Character: Int] = [:]
        var tLetterCount: [Character: Int] = [:]

        for i in s {
            if let count = sLetterCount[i] {
                sLetterCount[i] = count + 1
            } else {
                sLetterCount[i] = 1
            }
        }

        for i in t {
            if let count = tLetterCount[i] {
                tLetterCount[i] = count + 1
            } else {
                tLetterCount[i] = 1
            }
        }

        if sLetterCount.count != tLetterCount.count {
            return false
        }

        for (letter, count) in sLetterCount {
            if let value = tLetterCount[letter], count == value {
                continue
            } else {
                return false
            }
        }

        return true
    }
}

var solution = Solution()

var testcase1 = solution.isAnagram("anagram", "nagaram")
print(testcase1) // true

var testcase2 = solution.isAnagram("rat", "car")
print(testcase2) // false