string_patterns.cpp

/*
Hash Table & String Patterns
Mathematical Foundation: Hash functions O(1) avg, collision handling
Applications: Frequency counting, anagram detection, substring matching
Rolling hash: Rabin-Karp O(n+m), KMP O(n+m)
*/

#include <bits/stdc++.h>
using namespace std;

// Two Sum
// LeetCode: 1. Two Sum
// https://leetcode.com/problems/two-sum/
vector<int> twoSum(vector<int>& a, int target) {
    unordered_map<int,int> mp;
    for (int i = 0; i < a.size(); i++) {
        if (mp.count(target - a[i])) return {mp[target - a[i]], i};
        mp[a[i]] = i;
    }
    return {};
}

// Group Anagrams
// LeetCode: 49. Group Anagrams
// https://leetcode.com/problems/group-anagrams/
vector<vector<string>> groupAnagrams(vector<string>& strs) {
    unordered_map<string, vector<string>> mp;
    for (string& s : strs) {
        string key = s;
        sort(key.begin(), key.end());
        mp[key].push_back(s);
    }
    vector<vector<string>> res;
    for (auto& p : mp) res.push_back(p.second);
    return res;
}

// Valid Anagram
// LeetCode: 242. Valid Anagram
// https://leetcode.com/problems/valid-anagram/
bool isAnagram(string s, string t) {
    if (s.size() != t.size()) return false;
    vector<int> cnt(26);
    for (int i = 0; i < s.size(); i++) {
        cnt[s[i] - 'a']++;
        cnt[t[i] - 'a']--;
    }
    return all_of(cnt.begin(), cnt.end(), [](int x) { return x == 0; });
}

// Longest Substring Without Repeating Characters
// LeetCode: 3. Longest Substring Without Repeating Characters
// https://leetcode.com/problems/longest-substring-without-repeating-characters/
int lengthOfLongestSubstring(string s) {
    unordered_set<char> st;
    int l = 0, mx = 0;
    for (int r = 0; r < s.size(); r++) {
        while (st.count(s[r])) st.erase(s[l++]);
        st.insert(s[r]);
        mx = max(mx, r - l + 1);
    }
    return mx;
}

// Minimum Window Substring
// LeetCode: 76. Minimum Window Substring
// https://leetcode.com/problems/minimum-window-substring/
string minWindow(string s, string t) {
    unordered_map<char,int> need, have;
    for (char c : t) need[c]++;
    int l = 0, valid = 0, start = 0, len = INT_MAX;
    for (int r = 0; r < s.size(); r++) {
        char c = s[r];
        if (need.count(c)) {
            have[c]++;
            if (have[c] == need[c]) valid++;
        }
        while (valid == need.size()) {
            if (r - l + 1 < len) {
                start = l;
                len = r - l + 1;
            }
            char d = s[l];
            l++;
            if (need.count(d)) {
                if (have[d] == need[d]) valid--;
                have[d]--;
            }
        }
    }
    return len == INT_MAX ? "" : s.substr(start, len);
}

// Palindromic Substrings
// LeetCode: 647. Palindromic Substrings
// https://leetcode.com/problems/palindromic-substrings/
int countSubstrings(string s) {
    int cnt = 0;
    auto expand = [&](int l, int r) {
        while (l >= 0 && r < s.size() && s[l] == s[r]) {
            cnt++;
            l--;
            r++;
        }
    };
    for (int i = 0; i < s.size(); i++) {
        expand(i, i);
        expand(i, i + 1);
    }
    return cnt;
}

// Longest Palindromic Substring
// LeetCode: 5. Longest Palindromic Substring
// https://leetcode.com/problems/longest-palindromic-substring/
string longestPalindrome(string s) {
    string res;
    auto expand = [&](int l, int r) {
        while (l >= 0 && r < s.size() && s[l] == s[r]) {
            if (r - l + 1 > res.size()) res = s.substr(l, r - l + 1);
            l--;
            r++;
        }
    };
    for (int i = 0; i < s.size(); i++) {
        expand(i, i);
        expand(i, i + 1);
    }
    return res;
}

// Find All Anagrams in a String
// LeetCode: 438. Find All Anagrams in a String
// https://leetcode.com/problems/find-all-anagrams-in-a-string/
vector<int> findAnagrams(string s, string p) {
    if (s.size() < p.size()) return {};
    vector<int> res, need(26), have(26);
    for (char c : p) need[c - 'a']++;
    for (int i = 0; i < s.size(); i++) {
        have[s[i] - 'a']++;
        if (i >= p.size()) have[s[i - p.size()] - 'a']--;
        if (need == have) res.push_back(i - p.size() + 1);
    }
    return res;
}

// Substring with Concatenation of All Words
// LeetCode: 30. Substring with Concatenation of All Words
// https://leetcode.com/problems/substring-with-concatenation-of-all-words/
vector<int> findSubstring(string s, vector<string>& words) {
    if (words.empty()) return {};
    unordered_map<string,int> need;
    for (string& w : words) need[w]++;
    vector<int> res;
    int wlen = words[0].size(), n = words.size();
    for (int i = 0; i <= (int)s.size() - wlen * n; i++) {
        unordered_map<string,int> seen;
        int j = 0;
        for (; j < n; j++) {
            string word = s.substr(i + j * wlen, wlen);
            if (!need.count(word)) break;
            seen[word]++;
            if (seen[word] > need[word]) break;
        }
        if (j == n) res.push_back(i);
    }
    return res;
}

// Implement strStr() / KMP Algorithm
// LeetCode: 28. Implement strStr()
// https://leetcode.com/problems/implement-strstr/
int strStr(string s, string p) {
    if (p.empty()) return 0;
    vector<int> lps(p.size());
    for (int i = 1, j = 0; i < p.size(); i++) {
        while (j && p[i] != p[j]) j = lps[j - 1];
        if (p[i] == p[j]) lps[i] = ++j;
    }
    for (int i = 0, j = 0; i < s.size(); i++) {
        while (j && s[i] != p[j]) j = lps[j - 1];
        if (s[i] == p[j]) j++;
        if (j == p.size()) return i - j + 1;
    }
    return -1;
}

// Rolling Hash / Rabin-Karp
// LeetCode: 1392. Longest Happy Prefix
// https://leetcode.com/problems/longest-happy-prefix/
string longestPrefix(string s) {
    const int MOD = 1e9 + 7, BASE = 26;
    int n = s.size();
    long long prefix = 0, suffix = 0, pow = 1;
    int len = 0;
    for (int i = 0; i < n - 1; i++) {
        prefix = (prefix * BASE + s[i] - 'a') % MOD;
        suffix = (suffix + (s[n - 1 - i] - 'a') * pow) % MOD;
        pow = (pow * BASE) % MOD;
        if (prefix == suffix) len = i + 1;
    }
    return s.substr(0, len);
}

// Character Frequency Map
unordered_map<char,int> getFreq(string s) {
    unordered_map<char,int> freq;
    for (char c : s) freq[c]++;
    return freq;
}

// Check if strings are rotations of each other
bool isRotation(string s1, string s2) {
    return s1.size() == s2.size() && (s1 + s1).find(s2) != string::npos;
}