Skip to main content
CodePeet

CodePeet 444 Complete DSA Sheet

Frequency Counting with Hash Maps

Editorial

Count once, then answer

Valid Anagram: is "nagaram" a rearrangement of "anagram"? You could sort both and compare, O(n log n). Or ask the question the way it's really meant: does every letter appear the same number of times in both? That's a question about counts, and counts take one pass to build.

"anagram" has 3 a's, 1 n, 1 g, 1 r, 1 m, and so does "nagaram". "rat" and "car" don't match: rat has a t and no c.

Nearly every counting problem is the same two steps: build the counts once, then answer from them. The answer is one of three questions: are two count tables equal, is one big enough to cover the other, or which count is 1 (or 0)?

Letter counts for two pairs of words. "anagram" and "nagaram" have the same count for every letter (a 3, n 1, g 1, r 1, m 1), drawn as matching pairs of bars, so they're anagrams. "rat" and "car" match on r and a but not on t and c, so they aren't.

A map, or an array of 26

A count is a map from letter to number. When the letters are only a to z, the map can be a plain array of 26 slots: letter c lives at index c - 'a'. That's a hash table whose hash function never collides, and it's faster and smaller than a real one.

Use one array for both words: add for each letter of s, take away for each letter of t. If everything ends at 0, they match.

Counting "anagram" and "nagaram" — The table is the count for each letter: up for the first word, down for the second.

bool isAnagram(const string& s, const string& t) {
    if (s.size() != t.size()) return false;
    int count[26] = {0};                               // one slot per letter: an array is the hash table
    for (char c : s) count[c - 'a']++;                 // s adds its letters
    for (char c : t) count[c - 'a']--;                 // t takes them away
    for (int k = 0; k < 26; k++)
        if (count[k] != 0) return false;               // a letter left over, or one missing
    return true;
}

def is_anagram(s, t):
    if len(s) != len(t):
        return False
    count = [0] * 26                            # one slot per letter: an array is the hash table
    for c in s:
        count[ord(c) - ord('a')] += 1           # s adds its letters
    for c in t:
        count[ord(c) - ord('a')] -= 1           # t takes them away
    return all(k == 0 for k in count)           # nothing left over, nothing missing

static boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) return false;
    int[] count = new int[26];                         // one slot per letter: an array is the hash table
    for (char c : s.toCharArray()) count[c - 'a']++;   // s adds its letters
    for (char c : t.toCharArray()) count[c - 'a']--;   // t takes them away
    for (int k : count)
        if (k != 0) return false;                      // a letter left over, or one missing
    return true;
}

function isAnagram(s, t) {
    if (s.length !== t.length) return false;
    const count = new Array(26).fill(0);               // one slot per letter: an array is the hash table
    for (const c of s) count[c.charCodeAt(0) - 97]++;  // s adds its letters
    for (const c of t) count[c.charCodeAt(0) - 97]--;  // t takes them away
    return count.every(k => k === 0);                  // nothing left over, nothing missing
}

Each prints true, false, false, true and false for "anagram" and "nagaram", "rat" and "car", "a" and "ab", "ab" and "ba", and "aacc" and "ccac". It's O(n) time and O(1) extra space (26 slots, whatever the length).

When the input can hold any character (Valid Anagram's Unicode follow-up), swap the array for a real map: Counter in Python, HashMap<Character, Integer> in Java, unordered_map<char, int> in C++, Map in JavaScript. The algorithm doesn't change.

Is there enough?

Ransom Note: can you write ransomNote with letters cut from magazine, each used once? Count the magazine, then spend one letter for each letter of the note. If a count drops below 0, the magazine ran out.

from collections import Counter


def can_construct(ransom_note, magazine):
    have = Counter(magazine)                    # what the magazine offers
    for c in ransom_note:
        have[c] -= 1                            # spend one
        if have[c] < 0:
            return False                        # ran out of c
    return True

It prints False, False and True for "a" from "b", "aa" from "ab" and "aa" from "aab". It's the anagram check with one difference: the magazine may have letters left over.

Count, then scan

First Unique Character in a String: the index of the first letter that appears exactly once. In one pass you can't know yet: the next letter might repeat it. So take two. The first pass counts. The second walks the string again, in order, and stops at the first letter whose count is 1.

from collections import Counter


def first_uniq_char(s):
    count = Counter(s)                          # pass 1: how often each letter appears
    for i, c in enumerate(s):                   # pass 2: the string, in order
        if count[c] == 1:
            return i
    return -1

It prints 0, 2 and -1 for "leetcode", "loveleetcode" and "aabb". Both passes are O(n). Walk the string, not the map: a hash map's order isn't the string's order (see the second mistake below).

When the array is its own hash table

Find All Numbers Disappeared in an Array: nums has n values, each from 1 to n, some repeated; which of 1 to n are missing? A set of what you've seen works, with O(n) extra space. The follow-up asks for no extra space, and the values make that possible: every value v has a home, index v − 1.

So mark the home instead of storing v. For each value, make nums[v - 1] negative. The sign is the mark, and the number itself is still there (read it with abs), so marking never loses data. At the end, an index that's still positive was never anybody's home.

Marking [4, 3, 2, 7, 8, 2, 3, 1] — Each step reads a value (ignoring its sign) and marks its home index negative. The green indexes at the end were never marked.

vector<int> findDisappearedNumbers(vector<int>& nums) {
    for (int x : nums) {
        int i = abs(x) - 1;                            // x may already be marked: read its absolute value
        nums[i] = -abs(nums[i]);                       // mark "value i + 1 was seen"
    }
    vector<int> missing;
    for (int i = 0; i < (int)nums.size(); i++)
        if (nums[i] > 0) missing.push_back(i + 1);     // never marked: i + 1 never appeared
    return missing;
}

def find_disappeared_numbers(nums):
    for x in nums:
        i = abs(x) - 1                          # x may already be marked: read its absolute value
        nums[i] = -abs(nums[i])                 # mark "value i + 1 was seen"
    return [i + 1 for i, v in enumerate(nums) if v > 0]   # never marked: i + 1 never appeared

static List<Integer> findDisappearedNumbers(int[] nums) {
    for (int x : nums) {
        int i = Math.abs(x) - 1;                       // x may already be marked: read its absolute value
        nums[i] = -Math.abs(nums[i]);                  // mark "value i + 1 was seen"
    }
    List<Integer> missing = new ArrayList<>();
    for (int i = 0; i < nums.length; i++)
        if (nums[i] > 0) missing.add(i + 1);           // never marked: i + 1 never appeared
    return missing;
}

function findDisappearedNumbers(nums) {
    for (const x of nums) {
        const i = Math.abs(x) - 1;                     // x may already be marked: read its absolute value
        nums[i] = -Math.abs(nums[i]);                  // mark "value i + 1 was seen"
    }
    const missing = [];
    for (let i = 0; i < nums.length; i++)
        if (nums[i] > 0) missing.push(i + 1);          // never marked: i + 1 never appeared
    return missing;
}

Each prints the missing values, 5 6, 2, none, 1 3 and none, for [4, 3, 2, 7, 8, 2, 3, 1], [1, 1], [1], [2, 2, 2] and [5, 4, 3, 2, 1]. Two passes, O(n) time, O(1) extra space. The same trick solves Find All Duplicates in an Array (a home already marked means a duplicate) and First Missing Positive. It needs two things: values from 1 to n, and permission to change the input.

Counts that wait

Number of Matching Subsequences: how many of words are subsequences of s? Checking each word against all of s repeats the scan for every word. Instead, file each word under the next letter it needs, and walk s once. Each letter of s wakes exactly the words waiting for it; each of them moves on to wait for its following letter, or is done.

from collections import defaultdict


def num_matching_subseq(s, words):
    waiting = defaultdict(list)                 # next letter needed -> (word, how much of it is matched)
    for w in words:
        waiting[w[0]].append((w, 0))
    done = 0
    for c in s:
        ready, waiting[c] = waiting[c], []      # everyone waiting for c gets it now
        for w, k in ready:
            if k + 1 == len(w):
                done += 1                       # the whole word is matched
            else:
                waiting[w[k + 1]].append((w, k + 1))    # wait for its next letter
    return done

It prints 3 for s = "abcde" with "a", "bb", "acd" and "ace" (all but "bb"), and 2 for the problem's second example. Every letter of s and every letter of every word is handled once: O(len(s) + total length of the words). The map's keys are letters, its values are lists of words, and that's still a hash table.

Which counter to use

Clues: "anagram", "same letters", "rearrange" (equal counts), "can you build", "enough" (one count covers another), "first unique", "appears once", "most frequent" (which count).

  • Lowercase letters only: an array of 26.
  • Any characters, or numbers: a hash map (Counter in Python).
  • Values from 1 to n, and you may change the input: mark by index, O(1) extra space.
  • Many queries waiting on the next item: a map from that item to a list.

Near misses: counts inside a window that slides along the array belong to Introduction to Sliding Window (Find All Anagrams in a String), and counts of running sums belong to the Prefix Sum section.

Common mistakes

Subtracting Python Counters to compare them. Counter(s) - Counter(t) == Counter()

"ab" against "abc" gives True: subtraction keeps only positive counts, so the c that t has and s doesn't just disappears. (The other way round it gives False.) Compare the Counters directly: Counter(s) == Counter(t).

Finding "the first" by walking a hash map. for (auto& [c, k] : count) in C++

On "loveleetcode" it returned 10; the first unique letter is at index 2. An unordered_map (or Java's HashMap) walks its keys in bucket order, not in the order they arrived. Walk the string.

Marking without abs. i = x - 1

On [4, 3, 2, 7, 8, 2, 3, 1] it returns [2, 5] instead of [5, 6]. Once a value has been marked negative, x - 1 is negative too, and Python's negative index silently marks a slot counted from the end. In Java or C++ it's an out-of-bounds read. Read every value with abs.

An array of 26 on input that isn't lowercase. count[ord(c) - ord('a')]

On "Ab" and "bA" it crashes with IndexError: list index out of range: 'A' sits 32 places before 'a'. Check the constraints before reaching for 26 slots; otherwise use a map.

Check yourself

Quiz

1 / 5

Multiple choice

Valid Anagram with an array of 26: "aab" adds its letters, then "abb" takes its letters away. What's left?

Practice problems

From easier to harder:

  1. Element Frequency Count: build the counts.
  2. Valid Anagram: are two count tables equal?
  3. Ransom Note: does one count table cover the other?
  4. First Unique Character in a String: count, then scan the string.
  5. Sort Array by Increasing Frequency: count, then sort by count.
  6. Find All Numbers Disappeared in an Array: the array as its own table.
  7. Reorganize String: count, and check the most frequent letter fits.
  8. Number of Matching Subsequences: words waiting on their next letter.

Next: Grouping and Matching with Hash Maps.