Given two strings s and t, return true if t is an anagram of s, meaning it uses exactly the same letters the same number of times, possibly in a different order. Otherwise return false.
Example 1
Input: s = "anagram", t = "nagaram"
Output: true
Example 2
Input: s = "rat", t = "car"
Output: false
s has a t that t does not, and t has a c that s does not.Constraints
- 1 <= s.length, t.length <= 5 * 10^4
- Both strings contain only lowercase English letters
Hints
Frequently asked at: Amazon, Bloomberg, Microsoft, TCS, Accenture
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
Sorting both strings and comparing them is a correct O(n log n) solution. But two strings are anagrams exactly when their letter counts match, and with 26 lowercase letters a fixed array of counters does the job in one pass. Lengths must match first; then increment for s, decrement for t, and any non-zero counter means they differ.
Algorithm
- If the lengths differ, return
false. - Create
count[26]. - For each index
i, increasecount[s[i]]and decreasecount[t[i]]. - Return
trueonly if every counter is zero.
Time:
O(n)Space: O(1), 26 countersInterview tip: Follow-up: what if the inputs contain Unicode characters? Switch the fixed array for a hash map from character to count. Mention that the length check is a cheap early exit.
class Solution: def isAnagram(self, s: str, t: str) -> bool: if len(s) != len(t): return False count = [0] * 26 for a, b in zip(s, t): count[ord(a) - 97] += 1 count[ord(b) - 97] -= 1 return all(c == 0 for c in count)Ctrl + Enter runs the examples