242 : Valid Anagram #188
Description
Problem Number
242
Problem Title
Valid Anagram
LeetCode Link
https://leetcode.com/problems/valid-anagram/
Contribution Checklist
- I have written the Approach section.
- I have written the Intuition section.
- I have included a working C++ solution.
- I will raise a PR and ensure the filename follows the convention
[Number]. [Problem Title].cpp.
Approach
- Count the frequency of each character in the first string.
- Subtract the frequency using characters from the second string.
- If all counts are zero at the end, the strings are anagrams.
- Use vector of size 26 for lowercase letters (or unordered_map<char,int>).
- Time Complexity: O(n)
- Space Complexity: O(1)
Intuition
- An anagram has the same characters with the same frequency.
- By comparing character counts of both strings, we can check if one is a rearrangement of the other.
- This method avoids sorting and works in linear time.
Solution in C++
class Solution {
public:
bool isAnagram(string s, string t) {
if (s.length() != t.length()) {
return false;
}
vector<int> counts(26,0);
for (int i = 0; i < s.length(); ++i) {
// increment count for character in s & decrement for t
counts[s[i] - 'a']++;
counts[t[i] - 'a']--;
}
for (int count : counts) {
// check if all character counts net to zero
if (count != 0) {
return false;
}
}
return true; // all counts are zero, so it is an anagram..
}
};