Valid Anagram
EasyPrompt
Given two strings s and t, return true if t is an anagram of s, and false otherwise.
Example 1:
Input: s = "anagram", t = "nagaram"
Output: true
Example 2:
Input: s = "rat", t = "car"
Output: false
Constraints:
1 <= s.length, t.length <= 5 * 104sandtconsist of lowercase English letters.
Follow up: What if the inputs contain Unicode characters? How would you adapt your solution to such a case?
Approaches
2 approaches with complexity analysis and trade-offs.
Sort both strings and compare them character by character. If they are equal, then they are anagrams.
Algorithm
- Check if lengths of both strings are equal
- Convert strings to char arrays
- Sort both arrays
- Compare sorted arrays
Walkthrough
This approach involves sorting both strings and then comparing them. If two strings are anagrams, they will be equal after sorting.
public boolean isAnagram(String s, String t) { if (s.length() != t.length()) { return false; } char[] str1 = s.toCharArray(); char[] str2 = t.toCharArray(); Arrays.sort(str1); Arrays.sort(str2); return Arrays.equals(str1, str2);}First, we check if the lengths of both strings are equal. If not, they cannot be anagrams. Then, we convert both strings to character arrays and sort them. Finally, we compare the sorted arrays. If they are equal, the strings are anagrams.
Complexity
Time
O(n log n) where n is the length of the strings (due to sorting)
Space
O(n) where n is the length of the strings (for creating char arrays)
Trade-offs
Pros
Simple to implement
Easy to understand
Works with Unicode characters without modification
Cons
Not the most efficient solution
Modifies the original strings
Requires extra space for sorting
Use a hash table to count the frequency of characters in both strings. If the frequencies match for all characters, then they are anagrams.
Algorithm
- Check if lengths are equal
- Create frequency array of size 26
- Increment count for chars in first string
- Decrement count for chars in second string
- Check if all counts are zero
Walkthrough
This approach uses a hash table (array for lowercase English letters) to count character frequencies. We increment counts for the first string and decrement for the second string. If all counts are zero at the end, the strings are anagrams.
public boolean isAnagram(String s, String t) { if (s.length() != t.length()) { return false; } int[] charCount = new int[26]; for (int i = 0; i < s.length(); i++) { charCount[s.charAt(i) - 'a']++; charCount[t.charAt(i) - 'a']--; } for (int count : charCount) { if (count != 0) { return false; } } return true;}We first check if the lengths are equal. Then we use an array to count characters (increment for first string, decrement for second). Finally, we check if all counts are zero.
Complexity
Time
O(n) where n is the length of the strings
Space
O(1) as we use fixed size array of 26 characters
Trade-offs
Pros
More efficient than sorting approach
Single pass through both strings
Constant extra space for English letters
Cons
Limited to lowercase English letters in basic form
Needs modification for Unicode characters
Uses extra space for frequency array
Solutions
Solution
public class Solution { public bool IsAnagram(string s, string t) { if (s.Length != t.Length) { return false; } int[] cnt = new int[26]; for (int i = 0; i < s.Length; ++i) { ++cnt[s[i] - 'a']; --cnt[t[i] - 'a']; } return cnt.All(x => x == 0); }}class Solution {public boolean isAnagram(String s, String t) { if (s.length() != t.length()) { return false; } int[] cnt = new int[26]; for (int i = 0; i < s.length(); ++i) { ++cnt[s.charAt(i) - 'a']; --cnt[t.charAt(i) - 'a']; } for (int i = 0; i < 26; ++i) { if (cnt[i] != 0) { return false; } } return true; }}/** * @param {string} s * @param {string} t * @return {boolean} */ var isAnagram = function (s, t) { if (s.length !== t.length) { return false; } const cnt = new Array(26).fill(0); for (let i = 0; i < s.length; ++i) { ++cnt[s.charCodeAt(i) - " a ".charCodeAt(0)]; --cnt[t.charCodeAt(i) - " a ".charCodeAt(0)]; } return cnt.every((x) => x === 0); };class Solution {public: bool isAnagram(string s, string t) { if (s.size() != t.size()) { return false; } vector<int> cnt(26); for (int i = 0; i < s.size(); ++i) { ++cnt[s[i] - 'a']; --cnt[t[i] - 'a']; } return all_of(cnt.begin(), cnt.end(), [](int x) { return x == 0; }); }};class Solution: def isAnagram(self, s: str, t: str) -> bool: if len(s) != len(t): return False cnt = Counter(s) for c in t: cnt[c] -= 1 if cnt[c] < 0: return False return TrueVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.