Valid Anagram#

Given two strings, decide whether one is an anagram of the other. Two strings are anagrams when they contain exactly the same letters with the same counts, just arranged differently. Return true if they match and false otherwise.

Example#

Input: s = "anagram", t = "nagaram" Output: True, both use the same letters the same number of times.

Input: s = "rat", t = "car" Output: False.

Brute force#

Sort both strings and compare the sorted results. If they are equal, the strings are anagrams. Sorting dominates the cost.

• Time: O(n log n) for the sort.
• Space: O(n) for the sorted copies.

Optimal approach#

Count how often each character appears. If the strings differ in length they cannot be anagrams, so return early. Otherwise build a frequency map for the first string, then decrement counts while scanning the second string. If any count goes negative or a character is missing, they are not anagrams. Python’s collections.Counter makes this a one-liner comparison.

Python solution#

1from collections import Counter
2
3
4def is_anagram(s, t):
5    if len(s) != len(t):
6        return False
7    return Counter(s) == Counter(t)

Complexity#

• Time: O(n), one pass to count each string.
• Space: O(k), where k is the number of distinct characters (at most 26 for lowercase letters).

This problem is a clean use of the hashing pattern for frequency counting. Continue practicing with the 60-day challenge.