Coding interview problems › Arrays & Hashing

#️⃣ Arrays & Hashing Easy

Valid Anagram

Valid Anagram explained: compare character counts with a hash map in O(n) instead of sorting, with tested Python code, edge cases and a live visual.

Also searched as: check if two strings are anagrams · anagram program in python

#️⃣

Try it live Free

Hash Tables

Insert the characters as keys and watch each go straight to its bucket. Anagram checking is just counting how often each key arrives, which the hash table does in O(1) per character.

Open the playground →

The problem

Given two strings s and t, decide whether t is an anagram of s: it uses exactly the same letters, each the same number of times, possibly in a different order.

Inputs = "anagram", t = "nagaram"
OutputTrue
Inputs = "rat", t = "car"
OutputFalse

The key insight

Order does not matter, only how many of each character. So build a frequency count for one string, subtract the other, and check that every count lands on zero. Different lengths can be rejected immediately.

Brute force first: Sorting both strings and comparing works in O(n log n); it is a fine fallback but not the fastest.

Step-by-step approach

  1. If the lengths differ, return False.
  2. Count each character of s in a dictionary.
  3. For each character of t, decrement its count; if it goes below zero, t has an extra copy, so return False.
  4. Equal lengths plus no negative count means all counts are zero, so return True.

Python solution

PYTHON 3tested
def is_anagram(s, t):
    if len(s) != len(t):
        return False
    count = {}
    for ch in s:
        count[ch] = count.get(ch, 0) + 1
    for ch in t:
        if count.get(ch, 0) == 0:
            return False           # t uses ch more often than s
        count[ch] -= 1
    return True

Complexity

TimeO(n)
SpaceO(k)

Each string is scanned once. The dictionary holds one entry per distinct character k, which is at most 26 for lowercase English letters.

Common mistakes

Frequently asked questions

What is the time and space complexity of Valid Anagram?

The counting solution is O(n) time and O(k) space, where k is the alphabet size. Sorting both strings is O(n log n) time.

Can I use collections.Counter?

Yes, Counter(s) == Counter(t) is correct and O(n). In an interview, be ready to explain that it is building the same frequency map.

How do I handle Unicode or mixed case?

A dictionary works for any characters. Normalise first, for example with s.lower(), if the problem says case should be ignored.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Arrays & Hashing Hash Tables lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.