2Brute2Best
🔥0
02

Grouping by a canonical key (Arrays & Hashing Sub-pattern)

Turn each item into a canonical key — a form that's identical for everything in the same group — and bucket by that key.

Signals in the problem statement
  • ›

    "anagram"

  • ›

    "group strings that…"

  • ›

    "same letters / same pattern / same shape"

  • ›

    "no repeats in each row, column, box"

What makes it different

The work is in designing the key: sorted letters, a 26-count signature, or a computed id like the sudoku box (r / 3) * 3 + c / 3. A good key never puts two different groups together.

Questions

ordered from “learn the idea” to “recognise it without help”
  1. 1
    Valid Anagram
    Basic Anchor·LeetCode #242
    Easy
  2. 2
    Group Anagrams
    Slight Variation·LeetCode #49
    Medium
  3. 3
    Valid Sudoku
    Medium·LeetCode #36
    Medium

Template

grouping-template.cpp
// Group items that share a canonical key. Only keyOf() changes between problems.
string keyOf(const string& s) {
    int count[26] = {0};
    for (char c : s) count[c - 'a']++;
    string key;
    for (int x : count) key += to_string(x) + '#';  // '#' keeps "1,11" and "11,1" apart
    return key;
}

vector<vector<string>> groupByKey(vector<string>& items) {
    unordered_map<string, vector<string>> groups;
    for (auto& s : items) groups[keyOf(s)].push_back(s);
    vector<vector<string>> result;
    for (auto& [key, group] : groups) result.push_back(group);
    return result;
}
Remember this · Arrays & Hashing
Trigger
"Have I seen X before?", pairs that add up to a target, grouping things that look alike, counting occurrences.
Think
Instead of scanning again for each element, can I remember earlier elements in a map?
Key question
What exactly do I store as the key, and what as the value?
Complement lookupSet membership tricks