Minimal, copy-paste C++ for sliding window, two pointers, prefix sum, KMP, Manacher, and rolling hash.

Contents

Sliding Window (fixed/variable)

// Variable-size window (e.g., longest substring without repeating)
int longestNoRepeat(const string& s){
    vector<int> cnt(256, 0);
    int dup = 0, best = 0;
    for (int l = 0, r = 0; r < (int)s.size(); ++r){
        dup += (++cnt[(unsigned char)s[r]] == 2);
        while (dup > 0){
            dup -= (--cnt[(unsigned char)s[l++]] == 1);
        }
        best = max(best, r - l + 1);
    }
    return best;
}
ID Title Link Solution
3 Longest Substring Without Repeating Characters Link Solution
76 Minimum Window Substring Link -
392 Is Subsequence Link Solution
424 Longest Repeating Character Replacement Link -
616 Add Bold Tag in String Link Solution
681 Next Closest Time Link Solution

Two Pointers (sorted arrays/strings)

bool twoSumSorted(const vector<int>& a, int target){
    int l = 0, r = (int)a.size() - 1;
    while (l < r){
        long long sum = (long long)a[l] + a[r];
        if (sum == target) return true;
        if (sum < target) ++l; else --r;
    }
    return false;
}
ID Title Link Solution
15 3Sum Link -
11 Container With Most Water Link -
125 Valid Palindrome Link -

Binary Search on Answer (monotonic predicate)

long long binsearch(long long lo, long long hi){ // [lo, hi]
    auto good = [&](long long x){ /* check feasibility */ return true; };
    while (lo < hi){
        long long mid = (lo + hi) >> 1;
        if (good(mid)) hi = mid; else lo = mid + 1;
    }
    return lo;
}
ID Title Link Solution
33 Search in Rotated Sorted Array Link Solution
34 Find First and Last Position of Element in Sorted Array Link -
162 Find Peak Element Link -
875 Koko Eating Bananas Link -

Prefix Sum / Difference Array

vector<int> prefix(const vector<int>& a){
    vector<int> ps(a.size()+1);
    for (int i = 0; i < (int)a.size(); ++i) ps[i+1] = ps[i] + a[i];
    return ps;
}
ID Title Link Solution
303 Range Sum Query - Immutable Link Solution
523 Continuous Subarray Sum Link Solution
560 Subarray Sum Equals K Link -
238 Product of Array Except Self Link -
525 Contiguous Array Link Solution
1177 Can Make Palindrome from Substring Link Solution
370 Range Addition Link -

Hash Map Frequencies

unordered_map<int,int> freq;
for (int x: nums) ++freq[x];
ID Title Link Solution
1 Two Sum Link -
49 Group Anagrams Link -
242 Valid Anagram Link Solution
217 Contains Duplicate Link Solution
219 Contains Duplicate II Link Solution
383 Ransom Note Link Solution
981 Time Based Key-Value Store Link -
359 Logger Rate Limiter Link -

KMP is a pattern matching algorithm that finds occurrences of a pattern string P within a text string T efficiently — without re-checking characters that are already known to match.

While a naive substring search checks character-by-character and backtracks when a mismatch occurs (worst case O(n * m)), KMP preprocesses the pattern to know how far it can safely skip ahead when mismatches happen.

It does this using a “prefix function” (also called LPS — longest prefix which is also suffix).

Steps

Preprocess the pattern to build the lps[] array.

  • lps[i] = the length of the longest proper prefix of the substring P[0..i] which is also a suffix of this substring.

  • Proper prefix = prefix ≠ the string itself.

Use the LPS array during the search

  • When mismatch occurs, instead of resetting j = 0, we move j back to lps[j-1].
vector<int> kmpPi(const string& s) {
    int n = s.size();
    vector<int> pi(n);
    for (int i = 1; i < n; i++) {
        int j = pi[i - 1];
        while (j > 0 && s[i] != s[j]) j = pi[j - 1];
        if (s[i] == s[j]) j++;
        pi[i] = j;
    }
    return pi;
}
ID Title Link Solution
28 Find the Index of the First Occurrence in a String Link -
214 Shortest Palindrome Link -
686 Repeated String Match Link Solution

Manacher (Longest Palindromic Substring, O(n))

string manacher(const string& s) {
    string t = "|";
    for (char c : s) { t.push_back(c); t.push_back('|'); }
    int n = t.size();
    vector<int> p(n);
    int c = 0, r = 0, best = 0, center = 0;
    for (int i = 0; i < n; i++) {
        int mir = 2 * c - i;
        if (i < r) p[i] = min(r - i, p[mir]);
        while (i - 1 - p[i] >= 0 && i + 1 + p[i] < n && t[i - 1 - p[i]] == t[i + 1 + p[i]]) p[i]++;
        if (i + p[i] > r) { c = i; r = i + p[i]; }
        if (p[i] > best) { best = p[i]; center = i; }
    }
    int start = (center - best) / 2;
    return s.substr(start, best);
}
ID Title Link Solution
5 Longest Palindromic Substring Link -

Z-Algorithm (Pattern occurrences)

vector<int> zfunc(const string& s) {
    int n = s.size();
    vector<int> z(n);
    int l = 0, r = 0;
    for (int i = 1; i < n; i++) {
        if (i <= r) z[i] = min(r - i + 1, z[i - l]);
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++;
        if (i + z[i] - 1 > r) { l = i; r = i + z[i] - 1; }
    }
    return z;
}
ID Title Link Solution
1392 Longest Happy Prefix Link -

String Rolling Hash (Rabin–Karp)

struct RH {
    static const long long B = 911382323, M = 972663749;
    vector<long long> p, h;
    RH(const string& s) {
        int n = s.size();
        p.assign(n + 1, 1);
        h.assign(n + 1, 0);
        for (int i = 0; i < n; i++) {
            p[i + 1] = p[i] * B % M;
            h[i + 1] = (h[i] * B + s[i]) % M;
        }
    }
    long long get(int l, int r) {  // [l, r)
        return (h[r] - h[l] * p[r - l] % M + M) % M;
    }
};
ID Title Link Solution
187 Repeated DNA Sequences Link -
686 Repeated String Match Link Solution
1044 Longest Duplicate Substring Link -

More templates