Skip to main content
Ace Hired
All coding problems

Valid Anagram

Easyarrays hashingHash map frequency countstringhash-mapfrequency-count

Maintained by Vikas D, software engineer

You are handed two strings, s and t. Your job is to report whether t can be formed by shuffling the letters of s without adding or dropping any.

Two strings qualify as anagrams when every distinct character appears the same number of times in both. Order does not matter at all, only the tally of each character.

A quick consequence: if the two strings differ in length, they cannot be anagrams, since one side must hold a character the other lacks. The inputs here are lowercase English letters.

Examples

Input: s = "anagram", t = "nagaram"
Output: true

Both strings contain three a, one n, one g, one r, and one m, so t is just a reordering of s.

Input: s = "rat", t = "car"
Output: false

They share the same length, but s has a t while t (the string) has a c, so the letter tallies do not match.

Input: s = "ab", t = "a"
Output: false

The lengths differ, so no rearrangement of one can ever equal the other.

Constraints

  • 1 <= s.length, t.length <= 5 * 10^4
  • s and t consist only of lowercase English letters.

Visible test cases

  • isAnagram("anagram", "nagaram") == true
  • isAnagram("rat", "car") == false
  • isAnagram("a", "a") == true
  • isAnagram("ab", "a") == false
  • isAnagram("listen", "silent") == true
  • isAnagram("hello", "world") == false

Hints

Hint 1

If the two strings have different lengths, you can answer false right away.

Hint 2

Anagrams are about counts, not order. How could you record how many times each letter shows up?

Hint 3

Tally every character in s, then walk through t and decrement. If any count goes negative or a letter is missing, t is not an anagram.

Loading the editor...

Approaches

Sort and compare

Time O(n log n) · Space O(n)

Two strings are anagrams exactly when their sorted character sequences are identical.

  1. If the lengths differ, return false immediately.
  2. Sort the characters of s and the characters of t.
  3. Compare the two sorted sequences and return whether they are equal.

Frequency count with a hash map

Time O(n) · Space O(1) since at most 26 distinct lowercase letters are tracked

Count how often each character appears in s, then spend those counts down while scanning t; any shortfall means they are not anagrams.

  1. If the lengths differ, return false immediately.
  2. Walk through s and store a count per character in a map.
  3. Walk through t. For each character, if its stored count is zero or absent, return false; otherwise decrement it.
  4. If every character in t was matched, return true.

Common mistakes

  • Forgetting the length check. Without it, a string that is a prefix-by-counts of the other can slip through depending on how you compare.
  • Returning true as soon as one decrement succeeds rather than confirming the full pass over t.
  • Treating a missing key as count zero is fine, but accidentally creating the key (so it reads back as a falsy value you then decrement below zero) can corrupt later checks.
  • Assuming case or whitespace does not matter. Here the input is lowercase letters only, but a real interview variant may not be.

Follow-up variations

  • What changes if the strings can contain Unicode characters instead of just lowercase a to z?
  • How would you handle uppercase and lowercase as equal, or ignore spaces and punctuation?
  • Given many candidate strings, how would you group all anagrams of each other together efficiently?
  • Can you do it with a single fixed-size array of 26 counters instead of a hash map?

Recommended problems

Build the rest of your prep