LeetCode Templates: Arrays & Strings

Sliding Window (fixed/variable)
Two Pointers (sorted arrays/strings)
Binary Search on Answer
Prefix Sum / Difference Array
Hash Map Frequencies
KMP (Substring Search)
Manacher
Z-Algorithm
String Rolling Hash

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
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	-
981	Time Based Key-Value Store	Link	-
359	Logger Rate Limiter	Link	-

KMP (Substring Search)

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; // example
    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;
    }
};

ID	Title	Link	Solution
187	Repeated DNA Sequences	Link	-
686	Repeated String Match	Link	Solution
1044	Longest Duplicate Substring	Link	-

Robina Li