Hash Counting¶
Table of Contents¶
- 242. Valid Anagram (Easy)
- 560. Subarray Sum Equals K (Medium)
- 49. Group Anagrams (Medium)
- 438. Find All Anagrams in a String (Medium)
242. Valid Anagram¶
"""
- Return true if an input string is an anagram of another string.
- An anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once, e.g., `listen` is an anagram of `silent`.
"""
from collections import Counter
# Hashmap
def isAnagramHash(s: str, t: str) -> bool:
"""Return True if t is an anagram of s, False otherwise."""
if len(s) != len(t):
return False
count = dict()
for i in s:
if i in count:
count[i] += 1
else:
count[i] = 1
for j in t:
if j in count:
count[j] -= 1
else:
return False
for count in count.values():
if count != 0:
return False
return True
# Array
def isAnagramArray(s: str, t: str) -> bool:
if len(s) != len(t):
return False
count = [0 for _ in range(26)]
for i in s:
count[ord(i) - ord("a")] += 1
for j in t:
count[ord(j) - ord("a")] -= 1
for i in count:
if i != 0:
return False
return True
# Counter
def isAnagramCounter(s: str, t: str) -> bool:
return Counter(s) == Counter(t)
# |-------------|-----------------|--------------|
# | Approach | Time | Space |
# |-------------|-----------------|--------------|
# | Hashmap | O(n) | O(1) |
# | Array | O(n) | O(1) |
# | Counter | O(n) | O(1) |
# |-------------|-----------------|--------------|
s = "anagram"
t = "nagaram"
print(isAnagramHash(s, t)) # True
print(isAnagramArray(s, t)) # True
print(isAnagramCounter(s, t)) # True
#include <cassert>
#include <string>
#include <vector>
using namespace std;
class Solution {
public:
bool isAnagram(string s, string t) {
if (s.size() != t.size()) return false;
vector<int> count(26, 0);
for (char ch : s) count[ch - 'a']++;
for (char ch : t) count[ch - 'a']--;
for (int c : count) {
if (c != 0) return false;
}
return true;
}
};
int main() {
Solution solution;
assert(solution.isAnagram("anagram", "nagaram") == true);
assert(solution.isAnagram("rat", "car") == false);
assert(solution.isAnagram("a", "ab") == false);
assert(solution.isAnagram("a", "a") == true);
return 0;
}
560. Subarray Sum Equals K¶
from collections import defaultdict
from typing import List
# Prefix Sum
def subarraySum(nums: List[int], k: int) -> int:
preSums = defaultdict(int)
preSums[0] = 1
curSum = 0
res = 0
for num in nums:
curSum += num
res += preSums[curSum - k]
preSums[curSum] += 1
return res
nums = [1, 1, 1]
k = 2
print(subarraySum(nums, k)) # 2
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
int subarraySum(vector<int>& nums, int k) {
int n = nums.size();
vector<int> prefixSum(n + 1);
for (int i = 0; i < n; i++) {
prefixSum[i + 1] = prefixSum[i] + nums[i];
}
int res = 0;
unordered_map<int, int> cnt;
for (int ps : prefixSum) {
if (cnt.find(ps - k) != cnt.end()) res += cnt[ps - k];
cnt[ps]++;
}
return res;
}
int main() {
vector<int> nums = {1, 1, 1};
int k = 2;
cout << subarraySum(nums, k) << endl; // 2
return 0;
}
49. Group Anagrams¶
from collections import defaultdict
from typing import List
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
"""Counting Hash Map: O(n * k) time, O(n) space.
Words with the same 26-letter frequency tuple are anagrams.
"""
groups = defaultdict(list)
for word in strs:
counts = [0] * 26
for ch in word:
counts[ord(ch) - ord("a")] += 1
groups[tuple(counts)].append(word)
return list(groups.values())
def test_group_anagrams():
def normalized(groups):
return sorted(sorted(group) for group in groups)
s = Solution()
result = s.groupAnagrams(["eat", "tea", "tan", "ate", "nat", "bat"])
assert normalized(result) == [
["ate", "eat", "tea"],
["bat"],
["nat", "tan"],
]
assert normalized(s.groupAnagrams([""])) == [[""]]
assert normalized(s.groupAnagrams(["a"])) == [["a"]]
#include <algorithm>
#include <cassert>
#include <ranges>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string>> map;
for (string& s : strs) {
string sorted = s;
ranges::sort(sorted);
map[sorted].push_back(s);
}
vector<vector<string>> res;
for (auto& kv : map) {
res.push_back(kv.second);
}
return res;
}
};
int main() {
Solution solution;
vector<string> strs = {"eat", "tea", "tan"};
vector<vector<string>> res = solution.groupAnagrams(strs);
assert((res == vector<vector<string>>{{"eat", "tea"}, {"tan"}} ||
res == vector<vector<string>>{{"tan"}, {"eat", "tea"}}));
return 0;
}
438. Find All Anagrams in a String¶
from typing import List
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
"""Fixed Sliding Window: O(n + m) time, O(1) space.
Track 26 lowercase counts for the current window of length len(p).
"""
if len(p) > len(s):
return []
target = [0] * 26
window = [0] * 26
for i, ch in enumerate(p):
target[ord(ch) - ord("a")] += 1
window[ord(s[i]) - ord("a")] += 1
res = []
if window == target:
res.append(0)
left = 0
for right in range(len(p), len(s)):
window[ord(s[right]) - ord("a")] += 1
window[ord(s[left]) - ord("a")] -= 1
left += 1
if window == target:
res.append(left)
return res
def test_find_anagrams():
s = Solution()
assert s.findAnagrams("cbaebabacd", "abc") == [0, 6]
assert s.findAnagrams("abab", "ab") == [0, 1, 2]
assert s.findAnagrams("af", "be") == []
assert s.findAnagrams("baa", "aa") == [1]
assert s.findAnagrams("", "a") == []