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
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); }}Video 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.