Hashing

// C++ std::hash for built-in types
#include <functional>
 
hash<int>    intHash;
hash<string> strHash;
 
cout << intHash(42)          << "\n";  // Some large number
cout << strHash("interview") << "\n";  // Some large number
 
// Modulo to get bucket index
int buckets = 1000;
int idx = intHash(42) % buckets;

// Compute polynomial hash of a string
long long polyHash(const string& s, long long base = 31, long long mod = 1e9 + 7) {
    long long hash = 0, power = 1;
    for (char c : s) {
        hash  = (hash + (c - 'a' + 1) * power) % mod;
        power = (power * base) % mod;
    }
    return hash;
}
 
// Why 'a'+1 (1-indexed)? So that "a" and "aa" don't both start the same way.
// "a"  = 1·1         = 1
// "aa" = 1·1 + 1·31  = 32   (different from "a")

// What bad luck looks like (all keys map to same bucket):
unordered_map<int,int> mp;
// Adversarial input: all keys ≡ 0 (mod bucket_count)
// Every lookup degrades to O(n) list scan
// → Use map<int,int> instead when adversarial input is possible

unordered_map<int,int> mp;
mp.reserve(100000);      // Pre-allocate buckets — avoids repeated rehashing
mp.max_load_factor(0.25);  // Trigger rehash earlier → fewer collisions, more memory
 
cout << mp.load_factor();   // Current load factor
cout << mp.bucket_count();  // Current number of buckets

unordered_map<string, int> cnt;
 
// ❌ This inserts "missing_key" with value 0 if it doesn't exist
int val = cnt["missing_key"];   // Now cnt has a spurious entry
 
// ✅ Use find() for safe lookup
auto it = cnt.find("missing_key");
if (it != cnt.end()) {
    int val = it->second;
}
 
// ✅ Or use count() before accessing
if (cnt.count("missing_key")) {
    int val = cnt["missing_key"];
}

// ── Option 1: Fixed array — O(1) space for bounded character set ────────────
int freq[26] = {};                      // Lowercase a-z
int freq128[128] = {};                  // All ASCII characters
for (char c : s) freq[c - 'a']++;
 
// ── Option 2: unordered_map — General purpose, any hashable type ─────────────
unordered_map<int, int> cnt;
for (int x : nums) cnt[x]++;
 
// ── Option 3: sorted + count — When you need sorted traversal of results ─────
map<int, int> sortedCnt;
for (int x : nums) sortedCnt[x]++;

int firstUniqChar(string s) {
    int freq[26] = {};
    for (char c : s) freq[c - 'a']++;
    for (int i = 0; i < (int)s.size(); i++)
        if (freq[s[i] - 'a'] == 1) return i;
    return -1;
}
// Time: O(n), Space: O(1)

// Moore's Voting: if majority exists, it survives cancellation
int majorityElement(vector<int>& nums) {
    int candidate = nums[0], count = 1;
    for (int i = 1; i < (int)nums.size(); i++) {
        if (count == 0) { candidate = nums[i]; count = 1; }
        else count += (nums[i] == candidate) ? 1 : -1;
    }
    return candidate;  // Guaranteed to exist by problem statement
}
// Time: O(n), Space: O(1) — cleverly avoids hashing entirely

// Approach A: Freq map + Min-Heap — O(n log k)
vector<int> topKFrequent(vector<int>& nums, int k) {
    unordered_map<int,int> cnt;
    for (int x : nums) cnt[x]++;
 
    // Min-heap of size k: {frequency, value}
    priority_queue<pair<int,int>,
                   vector<pair<int,int>>,
                   greater<>> minPQ;
 
    for (auto& [val, freq] : cnt) {
        minPQ.push({freq, val});
        if ((int)minPQ.size() > k) minPQ.pop();  // Keep only top k
    }
 
    vector<int> result;
    while (!minPQ.empty()) {
        result.push_back(minPQ.top().second);
        minPQ.pop();
    }
    return result;
}
// Time: O(n log k), Space: O(n + k)

// Approach B: Bucket Sort — O(n) — frequencies are bounded by n
vector<int> topKFrequent(vector<int>& nums, int k) {
    unordered_map<int,int> cnt;
    for (int x : nums) cnt[x]++;
 
    // Bucket i holds all elements with frequency i
    int n = nums.size();
    vector<vector<int>> buckets(n + 1);
    for (auto& [val, freq] : cnt) buckets[freq].push_back(val);
 
    vector<int> result;
    for (int freq = n; freq >= 1 && (int)result.size() < k; freq--) {
        for (int val : buckets[freq]) {
            result.push_back(val);
            if ((int)result.size() == k) break;
        }
    }
    return result;
}
// Time: O(n), Space: O(n)

bool sameFrequency(const string& s, const string& t) {
    if (s.size() != t.size()) return false;
    int freq[26] = {};
    for (char c : s) freq[c-'a']++;
    for (char c : t) if (--freq[c-'a'] < 0) return false;
    return true;  // All frequencies match
}

vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int,int> seen;  // value → index
 
    for (int i = 0; i < (int)nums.size(); i++) {
        int complement = target - nums[i];
        if (seen.count(complement)) {
            return {seen[complement], i};
        }
        seen[nums[i]] = i;
    }
    return {};
}
// Time: O(n), Space: O(n)
// Why insert AFTER looking up? To handle the case where nums[i]*2 == target.
// We want a different index, not the same element twice.

// Count pairs (i, j) where i < j and nums[i] - nums[j] == k
int countPairsWithDiff(vector<int>& nums, int k) {
    unordered_map<int,int> freq;
    for (int x : nums) freq[x]++;
 
    int count = 0;
    for (auto& [val, f] : freq) {
        if (freq.count(val + k)) {
            count += f * freq[val + k];  // All pairs between the two groups
        }
    }
    // If k == 0, pairs are within the same group: C(freq, 2) = freq*(freq-1)/2
    if (k == 0) {
        count = 0;
        for (auto& [val, f] : freq)
            count += f * (f - 1) / 2;
    }
    return count;
}

int fourSumCount(vector<int>& A, vector<int>& B,
                 vector<int>& C, vector<int>& D) {
    unordered_map<int,int> abSum;
 
    // Store all A[i] + B[j] sums
    for (int a : A)
        for (int b : B)
            abSum[a + b]++;
 
    int count = 0;
    // For each C[k] + D[l], look for its negation
    for (int c : C)
        for (int d : D)
            count += abSum[-(c + d)];
 
    return count;
}
// Time: O(n²), Space: O(n²)
// Brute force would be O(n⁴) — this is a massive improvement

// Count subarrays with sum = k
int subarraySum(vector<int>& nums, int k) {
    unordered_map<int,int> prefixCount;
    prefixCount[0] = 1;   // Empty prefix
    int prefixSum = 0, count = 0;
    for (int x : nums) {
        prefixSum += x;
        count += prefixCount[prefixSum - k];
        prefixCount[prefixSum]++;
    }
    return count;
}
// Time: O(n), Space: O(n)

// Count subarrays with XOR = k
int subarrayXOR(vector<int>& nums, int k) {
    unordered_map<int,int> prefixCount;
    prefixCount[0] = 1;
    int xorSoFar = 0, count = 0;
    for (int x : nums) {
        xorSoFar ^= x;
        // prefixXOR[j] ^ prefixXOR[i] = k  →  prefixXOR[i] = prefixXOR[j] ^ k
        count += prefixCount[xorSoFar ^ k];
        prefixCount[xorSoFar]++;
    }
    return count;
}
// Time: O(n), Space: O(n)

// LC 525: Longest subarray with equal number of 0s and 1s
// Trick: treat 0 as -1, then find longest subarray with sum = 0
int findMaxLength(vector<int>& nums) {
    unordered_map<int,int> firstSeen;  // prefixSum → first index seen
    firstSeen[0] = -1;                 // Sum 0 seen before index 0
    int prefixSum = 0, maxLen = 0;
 
    for (int i = 0; i < (int)nums.size(); i++) {
        prefixSum += (nums[i] == 1) ? 1 : -1;
 
        if (firstSeen.count(prefixSum)) {
            maxLen = max(maxLen, i - firstSeen[prefixSum]);
        } else {
            firstSeen[prefixSum] = i;  // Store first occurrence only
        }
    }
    return maxLen;
}
// Time: O(n), Space: O(n)

// Universal template for "find subarray/longest subarray" with prefix property
//
// For COUNT problems:  map[prefix] = count
// For LENGTH problems: map[prefix] = first index
//
// Seed:  map[identity_value] = 0 (for count) or -1 (for length/index)
//        where identity_value = prefix value representing empty prefix
//
// Variants:
//   Sum = k:   prefixSum + x,  look up (prefixSum - k)
//   XOR = k:   prefixXOR ^ x,  look up (prefixXOR ^ k)
//   Mod = 0:   prefixSum + x,  look up (prefixSum % k) same bucket

// Sorted string signature (simpler, slightly slower: O(k log k) per string)
string signature(const string& s) {
    string sorted_s = s;
    sort(sorted_s.begin(), sorted_s.end());
    return sorted_s;
}
 
// Frequency tuple signature (O(k) per string, but harder to use as map key)
array<int,26> freqSignature(const string& s) {
    array<int,26> freq = {};
    for (char c : s) freq[c-'a']++;
    return freq;  // Can use as key in map<array<int,26>, ...>
}

vector<vector<string>> groupAnagrams(vector<string>& strs) {
    unordered_map<string, vector<string>> groups;
 
    for (const string& s : strs) {
        string key = s;
        sort(key.begin(), key.end());   // Sorted string as key
        groups[key].push_back(s);
    }
 
    vector<vector<string>> result;
    for (auto& [key, group] : groups) {
        result.push_back(group);
    }
    return result;
}
// Time: O(n · k log k) where n = number of strings, k = max string length
// Space: O(n · k)
 
/*
  Input: ["eat","tea","tan","ate","nat","bat"]
  Sorted keys:
    "eat" → "aet" → group with "tea","ate"
    "tan" → "ant" → group with "nat"
    "bat" → "abt" → alone
 
  Output: [["eat","tea","ate"],["tan","nat"],["bat"]]
*/

bool isIsomorphic(string s, string t) {
    if (s.size() != t.size()) return false;
 
    unordered_map<char,char> sToT, tToS;
 
    for (int i = 0; i < (int)s.size(); i++) {
        char sc = s[i], tc = t[i];
 
        if (sToT.count(sc)) {
            if (sToT[sc] != tc) return false;   // Inconsistent mapping
        } else {
            if (tToS.count(tc) && tToS[tc] != sc) return false;  // Not bijective
            sToT[sc] = tc;
            tToS[tc] = sc;
        }
    }
    return true;
}
// Time: O(n), Space: O(1) — at most 128 ASCII chars stored
 
/*
  s = "egg", t = "add"
  i=0: e→a, a→e  ✓
  i=1: g→d, d→g  ✓
  i=2: g→d  ✓ (consistent)
  → true
 
  s = "foo", t = "bar"
  i=0: f→b, b→f  ✓
  i=1: o→a, a→o  ✓
  i=2: o→? but o is already mapped to a, t[2]='r' ≠ 'a' → false
*/

// Check if pattern "abba" matches word string "dog cat cat dog"
bool wordPattern(string pattern, string s) {
    vector<string> words;
    stringstream ss(s);
    string word;
    while (ss >> word) words.push_back(word);
 
    if (pattern.size() != words.size()) return false;
 
    unordered_map<char,   string> charToWord;
    unordered_map<string, char>   wordToChar;
 
    for (int i = 0; i < (int)pattern.size(); i++) {
        char   p = pattern[i];
        string w = words[i];
 
        if (charToWord.count(p) && charToWord[p] != w) return false;
        if (wordToChar.count(w) && wordToChar[w] != p) return false;
        charToWord[p] = w;
        wordToChar[w] = p;
    }
    return true;
}
// Time: O(n), Space: O(n)

// Hash for pair<int, int>
struct PairHash {
    size_t operator()(const pair<int,int>& p) const {
        // Cantor pairing or bit-mixing
        size_t h1 = hash<int>{}(p.first);
        size_t h2 = hash<int>{}(p.second);
        // Combine: the 0x9e3779b9 constant is derived from golden ratio
        return h1 ^ (h2 << 32) ^ (h2 >> 32);
    }
};
 
unordered_map<pair<int,int>, int, PairHash> pairMap;
pairMap[{1, 2}] = 42;
pairMap[{3, 4}] = 99;

// Template hash combiner (equivalent to boost::hash_combine)
template <class T>
void hashCombine(size_t& seed, const T& v) {
    seed ^= hash<T>{}(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}
 
// Hash for pair<int,int>
struct PairHash {
    size_t operator()(const pair<int,int>& p) const {
        size_t seed = 0;
        hashCombine(seed, p.first);
        hashCombine(seed, p.second);
        return seed;
    }
};
 
// Hash for vector<int>
struct VectorHash {
    size_t operator()(const vector<int>& v) const {
        size_t seed = v.size();
        for (int x : v) hashCombine(seed, x);
        return seed;
    }
};
 
// Usage
unordered_map<pair<int,int>, int, PairHash> memo;
unordered_map<vector<int>,   int, VectorHash> vecMap;

// For pair<int,int>: encode as "a,b"
auto encode = [](int a, int b) {
    return to_string(a) + "," + to_string(b);
};
unordered_map<string, int> mp;
mp[encode(1, 2)] = 42;
 
// For small values, pack into long long
auto packLL = [](int a, int b) {
    return (long long)a * 1000000007LL + b;  // Assumes b < 1e9+7
};
unordered_map<long long, int> mp2;
mp2[packLL(1, 2)] = 42;

// When you need a pair/struct as a key and don't want to write a hash:
// Use map<pair<int,int>, int> — it uses operator< by default for pairs
map<pair<int,int>, int> pairMap;
pairMap[{1, 2}] = 42;   // O(log n) but always correct

// Rabin-Karp: find first occurrence of pattern in text
int rabinKarp(const string& text, const string& pattern) {
    int n = text.size(), m = pattern.size();
    if (m > n) return -1;
 
    const long long BASE = 31, MOD = 1e9 + 7;
 
    // Compute BASE^(m-1) mod MOD
    long long highPow = 1;
    for (int i = 0; i < m - 1; i++) highPow = highPow * BASE % MOD;
 
    // Hash of pattern
    long long patHash = 0;
    for (char c : pattern) patHash = (patHash * BASE + (c - 'a' + 1)) % MOD;
 
    // Hash of first window
    long long winHash = 0;
    for (int i = 0; i < m; i++)
        winHash = (winHash * BASE + (text[i] - 'a' + 1)) % MOD;
 
    // Slide window
    for (int i = 0; i <= n - m; i++) {
        if (winHash == patHash) {
            // Hash match — verify (handles false positives)
            if (text.substr(i, m) == pattern) return i;
        }
        if (i < n - m) {
            // Roll: remove text[i], add text[i+m]
            winHash = (winHash - (text[i] - 'a' + 1) * highPow % MOD + MOD) % MOD;
            winHash = (winHash * BASE + (text[i + m] - 'a' + 1)) % MOD;
        }
    }
    return -1;
}
// Time: O(n + m) average, O(n·m) worst case (hash collisions)
// Use double hashing (two different MODs) to make collisions astronomically rare

// Find all substrings of length k that appear more than once
vector<string> findDuplicateSubstrings(const string& s, int k) {
    const long long BASE = 31, MOD = 1e9 + 7;
    long long highPow = 1;
    for (int i = 0; i < k - 1; i++) highPow = highPow * BASE % MOD;
 
    unordered_map<long long, vector<int>> hashToIdx;  // hash → starting indices
    long long h = 0;
    for (int i = 0; i < k; i++) h = (h * BASE + (s[i] - 'a' + 1)) % MOD;
    hashToIdx[h].push_back(0);
 
    for (int i = k; i < (int)s.size(); i++) {
        h = (h - (s[i-k] - 'a' + 1) * highPow % MOD + MOD) % MOD;
        h = (h * BASE + (s[i] - 'a' + 1)) % MOD;
        hashToIdx[h].push_back(i - k + 1);
    }
 
    unordered_set<string> seen;
    vector<string> result;
    for (auto& [hash, indices] : hashToIdx) {
        if (indices.size() > 1) {
            string sub = s.substr(indices[0], k);
            if (!seen.count(sub)) {
                seen.insert(sub);
                result.push_back(sub);
            }
        }
    }
    return result;
}
// Time: O(n), Space: O(n)

// Find all 10-letter DNA sequences that appear more than once
vector<string> findRepeatedDnaSequences(string s) {
    if (s.size() <= 10) return {};
 
    unordered_map<string, int> seen;
    vector<string> result;
 
    for (int i = 0; i + 10 <= (int)s.size(); i++) {
        string sub = s.substr(i, 10);
        if (++seen[sub] == 2) result.push_back(sub);
    }
    return result;
}
// Time: O(n · 10) = O(n), Space: O(n)
 
// Optimized: encode each letter as 2 bits (A=0, C=1, G=2, T=3)
// Entire 10-letter window fits in a 20-bit integer
vector<string> findRepeatedDnaSequences_Optimized(string s) {
    unordered_map<char,int> enc = {{'A',0},{'C',1},{'G',2},{'T',3}};
    unordered_map<int,int> seen;
    vector<string> result;
    int n = s.size();
    int mask = (1 << 20) - 1;  // 20-bit mask
 
    int hash = 0;
    for (int i = 0; i < 10; i++) hash = (hash << 2) | enc[s[i]];
    seen[hash]++;
 
    for (int i = 10; i < n; i++) {
        hash = ((hash << 2) | enc[s[i]]) & mask;  // Slide window
        if (++seen[hash] == 2) result.push_back(s.substr(i - 9, 10));
    }
    return result;
}
// Time: O(n), Space: O(n)

vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int,int> seen;
    for (int i = 0; i < (int)nums.size(); i++) {
        int comp = target - nums[i];
        if (seen.count(comp)) return {seen[comp], i};
        seen[nums[i]] = i;
    }
    return {};
}
// Time: O(n), Space: O(n)
// Key: insert AFTER lookup to avoid using same element twice when nums[i]*2 = target

int firstUniqChar(string s) {
    int freq[26] = {};
    for (char c : s) freq[c-'a']++;
    for (int i = 0; i < (int)s.size(); i++)
        if (freq[s[i]-'a'] == 1) return i;
    return -1;
}
// Time: O(n), Space: O(1)

bool isIsomorphic(string s, string t) {
    int sMap[128] = {}, tMap[128] = {};
    for (int i = 0; i < (int)s.size(); i++) {
        if (sMap[(int)s[i]] != tMap[(int)t[i]]) return false;
        sMap[(int)s[i]] = tMap[(int)t[i]] = i + 1;  // i+1 so 0 means "unseen"
    }
    return true;
}
// Time: O(n), Space: O(1) — two fixed 128-element arrays

vector<vector<string>> groupAnagrams(vector<string>& strs) {
    unordered_map<string, vector<string>> groups;
    for (const string& s : strs) {
        string key = s;
        sort(key.begin(), key.end());
        groups[key].push_back(s);
    }
    vector<vector<string>> result;
    for (auto& [key, grp] : groups) result.push_back(grp);
    return result;
}
// Time: O(n·k log k), Space: O(n·k)  — n strings, max length k

vector<int> topKFrequent(vector<int>& nums, int k) {
    unordered_map<int,int> cnt;
    for (int x : nums) cnt[x]++;
 
    // Bucket sort: bucket[freq] = list of values with that frequency
    int n = nums.size();
    vector<vector<int>> buckets(n + 1);
    for (auto& [val, freq] : cnt) buckets[freq].push_back(val);
 
    vector<int> result;
    for (int f = n; f >= 1 && (int)result.size() < k; f--)
        for (int val : buckets[f]) {
            result.push_back(val);
            if ((int)result.size() == k) return result;
        }
    return result;
}
// Time: O(n), Space: O(n)

int longestConsecutive(vector<int>& nums) {
    unordered_set<int> numSet(nums.begin(), nums.end());
    int maxLen = 0;
 
    for (int num : numSet) {
        // Only start a sequence from its first element
        if (!numSet.count(num - 1)) {
            int curr = num, len = 1;
            while (numSet.count(curr + 1)) { curr++; len++; }
            maxLen = max(maxLen, len);
        }
    }
    return maxLen;
}
// Time: O(n) amortized — each number is visited at most twice
// Space: O(n)
 
/*
  nums = [100, 4, 200, 1, 3, 2]
  numSet = {100, 4, 200, 1, 3, 2}
 
  num=100: no 99 in set → start sequence: 100 → length 1
  num=4:   3 is in set  → NOT a start, skip
  num=200: no 199       → start: 200 → length 1
  num=1:   no 0         → start: 1→2→3→4 → length 4  ✅
  num=3:   2 is in set  → skip
  num=2:   1 is in set  → skip
  Answer: 4
*/

int subarraySum(vector<int>& nums, int k) {
    unordered_map<int,int> prefixCnt;
    prefixCnt[0] = 1;
    int prefixSum = 0, count = 0;
    for (int x : nums) {
        prefixSum += x;
        count += prefixCnt[prefixSum - k];
        prefixCnt[prefixSum]++;
    }
    return count;
}
// Time: O(n), Space: O(n)

int findMaxLength(vector<int>& nums) {
    unordered_map<int,int> firstSeen;
    firstSeen[0] = -1;
    int balance = 0, maxLen = 0;
 
    for (int i = 0; i < (int)nums.size(); i++) {
        balance += (nums[i] == 1) ? 1 : -1;
        if (firstSeen.count(balance))
            maxLen = max(maxLen, i - firstSeen[balance]);
        else
            firstSeen[balance] = i;
    }
    return maxLen;
}
// Time: O(n), Space: O(n)
// Treat 0 as -1: equal 0s and 1s ↔ subarray sum = 0 ↔ same prefix balance

int fourSumCount(vector<int>& A, vector<int>& B,
                 vector<int>& C, vector<int>& D) {
    unordered_map<int,int> abSum;
    for (int a : A) for (int b : B) abSum[a + b]++;
    int count = 0;
    for (int c : C) for (int d : D) count += abSum[-(c + d)];
    return count;
}
// Time: O(n²), Space: O(n²)  — n = array length (all same size)

vector<string> findRepeatedDnaSequences(string s) {
    unordered_map<string,int> cnt;
    vector<string> result;
    for (int i = 0; i + 10 <= (int)s.size(); i++) {
        string sub = s.substr(i, 10);
        if (++cnt[sub] == 2) result.push_back(sub);
    }
    return result;
}
// Time: O(n), Space: O(n)

int longestPalindrome(string s) {
    int freq[128] = {};
    for (char c : s) freq[(int)c]++;
 
    int length = 0;
    bool hasOdd = false;
    for (int f : freq) {
        length += f / 2 * 2;  // Use as many pairs as possible
        if (f % 2 == 1) hasOdd = true;
    }
    return length + (hasOdd ? 1 : 0);  // One odd-freq char can be in the center
}
// Time: O(n), Space: O(1)

int minimumPushes(string word) {
    int freq[26] = {};
    for (char c : word) freq[c-'a']++;
 
    // Sort frequencies in descending order
    vector<int> freqs(freq, freq+26);
    sort(freqs.rbegin(), freqs.rend());
 
    int totalPresses = 0;
    for (int i = 0; i < 26; i++) {
        if (freqs[i] == 0) break;
        // Letters assigned to positions 1-8, 9-16, 17-24 require 1,2,3 presses
        int presses = i / 8 + 1;
        totalPresses += freqs[i] * presses;
    }
    return totalPresses;
}
// Time: O(n + 26 log 26) = O(n), Space: O(1)