LeetCode #242. Valid Anagram
Time Complexity O(n);
Space Complexity O(k) where k ≤ n, worst case O(n)
Number of map entries = number of unique characters = k
k can range from 1 to n
Space complexity: O(k) where k ≤ n
So while all n characters are processed, you only store the unique ones with their counts.
class Solution {
public boolean isAnagram(String s, String t) {
if (s.length() != t.length()) {
return false;
}
Map<Character, Integer> mapS = new HashMap<>();
for (char c : s.toCharArray()) {
mapS.put(c, mapS.getOrDefault(c, 0) +1);
}
Map<Character, Integer> mapT = new HashMap<>();
for (char c : t.toCharArray()) {
mapT.put(c, mapT.getOrDefault(c, 0) +1);
}
return mapT.equals(mapS);
}
}
