242. Valid Anagram
easyDetermine whether two strings are anagrams of each other. Tests character-frequency counting and the time/space tradeoff between sorting and a counter array.
By Alex Chen, 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^4s and t consist of lowercase English letters.
Examples
Example 1
s = "anagram", t = "nagaram"trueExample 2
s = "rat", t = "car"falseSolve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
Hints
Progressive — try the first before opening the next.
Hint 1
If the lengths differ, they can't be anagrams — early return.
Hint 2
Sorting both strings is correct but O(n log n).
Hint 3
Build a 26-element frequency array (or hash map). Increment for each char in s, decrement for each char in t. All zeros at the end means anagram.
Solution approach
Reveal approach
Quick length check first — different lengths means false. Then build a frequency counter (a 26-element int array works for lowercase English; a hash map handles Unicode). Walk s incrementing each character's count, then walk t decrementing. If any counter goes negative during the t scan, return false. Alternatively check all counters are zero at the end. One O(n) pass per string, O(1) extra space for the 26-letter case.
Complexity
- Time
- O(n)
- Space
- O(1)
Related patterns
- hash-map
Related problems
Asked at
Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).
- Amazon
- Bloomberg
- Microsoft
Practice these live with InterviewChamp.AI
Drill Valid Anagram and Strings problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.
Practice these live with InterviewChamp.AI →