Skip to main content

242. Valid Anagram

easy

Decide whether two strings are anagrams of each other. The clean hash-table version of a classic — count characters in one, decrement with the other, check zero. Solid warm-up for letter-counting patterns.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

Given two strings s and t, return true if t is an anagram of s, and false otherwise. An anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Constraints

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

Examples

Example 1

Input
s = 'anagram', t = 'nagaram'
Output
true

Example 2

Input
s = 'rat', t = 'car'
Output
false

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Length mismatch -> automatic false. Cheapest early exit.

Hint 2

Count characters in s; subtract counts using t. If any count is nonzero at the end, return false.

Hint 3

For lowercase English only, a length-26 int array beats a hash map on constant-factor performance.

Solution approach

Reveal approach

If s.length != t.length, return false. Maintain a length-26 array (or hash map). Walk s incrementing count[c - 'a']; walk t decrementing the same slots. Then iterate the count array; if any slot is nonzero, return false. Otherwise return true. Single-pass alternative: combine both loops, then scan counts at the end. For Unicode input use a hash map instead of a fixed 26-slot array. Sorting s and t and comparing for equality is O(n log n) but more readable; the count-array version is O(n) and uses O(1) space.

Complexity

Time
O(n)
Space
O(1)

Related patterns

  • hash-table
  • counting
  • string

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Meta
  • Bloomberg

More Hash Tables practice problems

See all Hash Tables problems →