Valid Anagram easy
Description
Given two strings s and t, return true if t is an anagram of s, and false otherwise.
An anagram is a word formed by rearranging the letters of a different word, using all the original letters exactly once.
Examples
> Case 1:
Input: s = "anagram", t = "nagaram"
Output: true
> Case 2:
Input: s = "rat", t = "car"
Output: falseConstraints
1 <= s.length, t.length <= 5 * 10^4sandtconsist of lowercase English letters
Follow up: What if the inputs contain Unicode characters?
Approach 1: Sorting
If two strings are anagrams, their sorted versions are identical.
Approach 2: Character Frequency Array (Optimal)
Count character frequencies in s, then subtract frequencies in t. If all counts are zero, they are anagrams.
Anagram check: "anagram" vs "nagaram"
Step 1 of 4
0
[0]0
[1]0
[2]0
[3]0
[4]0
[5]0
[6]0
[7]0
[8]0
[9]0
[10]0
[11]0
[12]0
[13]0
[14]0
[15]0
[16]0
[17]0
[18]0
[19]0
[20]0
[21]0
[22]0
[23]0
[24]0
[25]Start with freq[26] = all zeros. Process 'anagram': a:3, g:1, m:1, n:1, r:1.
Explanation
- Early return if lengths differ (can’t be anagrams)
- Use a 26-element array to count character frequencies
- Increment for each character in
s, decrement for each character int - If all counts end up at zero, both strings have identical character compositions
Follow-up answer: For Unicode characters, replace the fixed-size array with
a hash map (unordered_map in C++, Counter in Python, HashMap in Java).
The time complexity stays O(n) but space becomes O(k) where k is the number of
distinct characters.
Analysis
- Time Complexity:
O(n)— two passes through the strings - Space Complexity:
O(1)— fixed 26-element array (constant regardless of input size)