Minimal, copy-paste Java 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)
static int longestNoRepeat(String s){
    int[] cnt = new int[256];
    int dup = 0, best = 0;
    for (int l = 0, r = 0; r < (int)s.size(); ++r){
        dup += (++cnt[(int char)s[r]] == 2);
        while (dup > 0){
            dup -= (--cnt[(int char)s[l++]] == 1);
        }
        best = Math.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
713 Subarray Product Less Than K Link Solution
2461 Maximum Sum of Distinct Subarrays With Length K Link Solution

Two Pointers (sorted arrays/strings)

static boolean twoSumSorted(int[] a, int target){
    int l = 0, r = (int)a.size() - 1;
    while (l < r){
        long sum = (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 -
1768 Merge Strings Alternately Link Solution

Binary Search on Answer (monotonic predicate)

static long binsearch(long lo, long hi){ // [lo, hi]
    var good = [&](long x){ /* check feasibility */ return true; }
    while (lo < hi){
        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 -
1870 Minimum Speed to Arrive on Time Link Solution

Prefix Sum / Difference Array

int[]prefix(int[] a){
    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 -
134 Gas Station Link Solution
2270 Number of Ways to Split Array Link Solution

Hash Map Frequencies

// import java.util.*;
HashMap<Integer, Integer> freq = new HashMap<Integer, Integer>();
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 -
2365 Task Scheduler II Link Solution
2342 Max Sum of a Pair With Equal Sum of Digits Link Solution

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].
int[]kmpPi(String s) {
    int n = s.size();
    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))

static String manacher(String s) {
    String t = "|";
    for (char c : s) { t.add(c); t.add('|'); }
    int n = t.size();
    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] = Math.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.put(i, p.getOrDefault(i, 0) + 1);
        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)

int[]zfunc(String s) {
    int n = s.size();
    int[]z(n);
    int l = 0, r = 0;
    for (int i = 1; i < n; i++) {
        if (i <= r) z[i] = Math.min(r - i + 1, z[i - l]);
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z.put(i, z.getOrDefault(i, 0) + 1);
        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)

class RH {
    public static long B = 911382323, M = 972663749;
    long[]p, h;
    RH(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 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