Notes

242. Valid Anagram

3 min read

Prompt

Given two strings s and t, return true if t is an of s, and false otherwise.

  • Contraints
    • 1 <= s.length, t.length <= 5 * 104
    • s and t consist of lowercase English letters.

Examples

  • Example 1:
    • Input: s = “anagram”, t = “nagaram”
    • Output: true
  • Example 2:
    • Input: s = “rat”, t = “car”
    • Output: false

Solutions

HashMap Frequency Map Solution

In C++

bool isAnagram(string s, string t) {
	if (s.size() != t.size()) return false;
 
	unordered_map<char, size_t> frequency_map_a;
	for (char c : s) frequency_map_a[c]++;
 
	unordered_map<char, size_t> frequency_map_b;
	for (char c : t) frequency_map_b[c]++;
 
	return frequency_map_a == frequency_map_b;
}

Explanation

The idea here is that we create a frequency map for each string; a map of characters to how many times they appear in the string. If these two maps are the same, then the strings have identical frequencies for all characters, which is equivalent to them being anagrams.

This method works regardless of the constraint of the strings only containing lowercase English letters, i.e. for unicode.

Big O Analysis

Time Complexity

The time complexity is where is the length of either string. It is amortized because we are inserting into a HashMap, which can resize. See Amortized Notation.

Auxiliary Space Complexity

The space complexity is where is the set of characters between t and s.

Zero Heap Allocation Frequency Map Solution

In C++

bool isAnagram(string s, string t) {
	if (s.size() != t.size()) return false;
	
	unsigned int c[26] = {};
	for (size_t i = 0; i < s.size(); ++i) {
		++c[s[i] - 'a'];
		--c[t[i] - 'a'];
	}
	for (size_t i = 0; i < 26; ++i) {
		if (c[i] != 0) return false;
	}
	return true;
}

Explanation

The idea here is similar to the previous, except we really abuse and lean into the constraint of the strings only containing lowercase English letters. Based on this assumption, we can avoid Heap Allocation by basically simulating the HashMap, but with the amazing Hash Function of subtracting ‘a’ from each character, which maps a-z to 0-25, i.e. perfectly into a static sized 26 Array. We still use the array as a frequency map, but we suubtract instead of adding for the second string. In this way, if the strings have identical frequencies, the final array will be zeroed out.

Big O Analysis

Time Complexity

The time complexity is where is the length of either string.

Auxiliary Space Complexity

The space complexity is because space usage has no relation to the inputs.

Graph View