LeetCode 242 - Valid Anagram

This is an Easy string problem about checking whether two strings are built from the same characters. It is a good small comparison between sorting the strings and counting character frequencies.

Problem link and explanation

Problem link: 242. Valid Anagram
Summary: Given two strings s and t, return true if they are anagrams and false otherwise.

An anagram uses the same characters with the same counts. The order can be different, but each character must appear the same number of times.

For example:

s = "anagram"
t = "nagaram"

The order is different, but the character counts are the same, so the result is true.

A different example:

s = "rat"
t = "car"

The lengths are the same, but the character composition is different, so the result is false.

The first approach that comes to mind is sorting both strings. Since an anagram is the same set of characters in a different order, sorting both strings by the same rule should produce the same result. Sorting works, but it has a cost. If I only need to compare character counts, I can avoid sorting entirely.

Approach

1. Sort and compare

The most direct solution is to sort both strings and compare the results. If the two strings contain the same characters with the same counts, their sorted forms will match.

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

This version is short and clear. I do not need a separate length check because strings with different lengths will not have the same sorted result.

The cost is sorting. Sorting a string of length n takes O(n log n) time, and Python’s sorted function creates a new sorted list, so it also needs additional space.

2. Store character counts

To avoid sorting, I can count how many times each character appears. First, I scan s and store each character count in a dictionary. Then I scan t and subtract from those counts.

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

        char_map: Dict[str, int] = {}
        for ch in s:
            char_map[ch] = char_map.get(ch, 0) + 1

        for ch in t:
            if ch not in char_map or char_map[ch] == 0:
                return False

            char_map[ch] -= 1

        return True

If the lengths are different, the strings cannot be anagrams, so I return early. After that, the count table built from s becomes the reference, and each character in t cancels out one count.

The important check is whether the current character is missing from the count table or whether its remaining count is already zero. If t contains a character that never appeared in s, or contains a character more times than s did, the strings are not anagrams.

Complexity analysis

1. Sorting

Time complexity: O(n log n)
- Sorting dominates the cost, where n is the string length.
Space complexity: O(n)
- Python’s sorted function creates a new sorted list.

2. Character count

Time complexity: O(n + m)
- The solution scans s and t once each. Since the length check rejects different lengths early, this is usually summarized as O(n).
Space complexity: O(k)
- The dictionary stores only the characters that appear. Here, k is the number of distinct characters, and in the worst case it can grow with the input size. If the input is limited to lowercase English letters, a fixed array of length 26 can store the same counts, making the memory use fixed by the character set size.

Implementation code

I used the character count approach as the final implementation. It is a little longer than sorting, but it avoids sorting the strings and compares the character counts directly.

from typing import Dict

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

        char_map: Dict[str, int] = {}

        for ch in s:
            char_map[ch] = char_map.get(ch, 0) + 1

        for ch in t:
            if ch not in char_map or char_map[ch] == 0:
                return False

            char_map[ch] -= 1

        return True

Summary and reflection

The main shift in this problem is treating an anagram as a character count problem instead of an ordering problem. Sorting makes both strings follow the same order before comparison, while character counting compares the number of occurrences directly.

The sorting solution is simple and hard to get wrong, but it costs O(n log n) time. With a dictionary, I can count and cancel characters in O(n) time. If the character set is restricted to lowercase English letters, a length-26 array is another option and uses a smaller fixed amount of memory than a hash map. In this problem, keeping character counts is the more direct way to decide whether the two strings are anagrams.