Valid Anagram

Given two strings s and t, return True if t is an anagram of s — i.e. t uses exactly the same letters as s, each the same number of times.

Examples

Input:  s = "anagram", t = "nagaram"   -> True
Input:  s = "rat",     t = "car"       -> False

Constraints

• 1 <= len(s), len(t) <= 5 * 10^4, lowercase English letters.

Approach — compare letter frequencies

Anagrams have identical letter counts. If the two strings differ in length they can't be anagrams (quick reject). Otherwise, count letters in s and subtract counts for t; every tally must end at zero.

Solution

from collections import Counter

def is_anagram(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False
    return Counter(s) == Counter(t)

Manual counting (shows the mechanics without Counter):

def is_anagram(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False
    counts = {}
    for ch in s:
        counts[ch] = counts.get(ch, 0) + 1
    for ch in t:
        if counts.get(ch, 0) == 0:
            return False
        counts[ch] -= 1
    return True

Explanation

• The length check is a cheap early exit — no point counting if lengths differ.
• Counter(s) == Counter(t) compares two frequency maps for equality directly.
• In the manual version, if any letter in t is missing or over-used, a count hits zero and we reject. If we finish, every letter matched exactly.

Complexity

• Time: O(n).
• Space: O(1) — at most 26 distinct lowercase keys (bounded alphabet).

Interview tips

If Unicode is allowed, space becomes O(k) for k distinct characters. A sorting solution (sorted(s) == sorted(t)) also works but is O(n log n) — mention counting is faster.