Contents
Sliding Window (fixed/variable)
# Variable-size window (e.g., longest substring without repeating)
def longest_no_repeat(s: str) -> int:
cnt = [0] * 256
dup = 0
best = 0
l = 0
for r in range(len(s)):
cnt[ord(s[r])] += 1
if cnt[ord(s[r])] == 2:
dup += 1
while dup > 0:
cnt[ord(s[l])] -= 1
if cnt[ord(s[l])] == 1:
dup -= 1
l += 1
best = max(best, r - l + 1)
return best
Two Pointers (sorted arrays/strings)
def two_sum_sorted(a: list[int], target: int) -> bool:
l, r = 0, len(a) - 1
while l < r:
s = a[l] + a[r]
if s == target:
return True
if s < target:
l += 1
else:
r -= 1
return False
Binary Search on Answer (monotonic predicate)
def bin_search(lo: int, hi: int) -> int: # [lo, hi]
def good(x: int) -> bool:
# check feasibility
return True
while lo < hi:
mid = (lo + hi) >> 1
if good(mid):
hi = mid
else:
lo = mid + 1
return lo
Prefix Sum / Difference Array
def prefix(a: list[int]) -> list[int]:
ps = [0] * (len(a) + 1)
for i in range(len(a)):
ps[i + 1] = ps[i] + a[i]
return ps
Hash Map Frequencies
from collections import Counter
freq = Counter(nums)
# or manually:
freq = {}
for x in nums:
freq[x] = freq.get(x, 0) + 1
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].
def kmp_pi(s: str) -> list[int]:
n = len(s)
pi = [0] * n
for i in range(1, n):
j = pi[i - 1]
while j > 0 and s[i] != s[j]:
j = pi[j - 1]
if s[i] == s[j]:
j += 1
pi[i] = j
return pi
Manacher (Longest Palindromic Substring, O(n))
def manacher(s: str) -> str:
t = "|" + "|".join(s) + "|"
n = len(t)
p = [0] * n
c = r = best = center = 0
for i in range(n):
mir = 2 * c - i
if i < r:
p[i] = min(r - i, p[mir])
while i - 1 - p[i] >= 0 and i + 1 + p[i] < n and t[i - 1 - p[i]] == t[i + 1 + p[i]]:
p[i] += 1
if i + p[i] > r:
c = i
r = i + p[i]
if p[i] > best:
best = p[i]
center = i
start = (center - best) // 2
return s[start:start + best]
Z-Algorithm (Pattern occurrences)
def z_func(s: str) -> list[int]:
n = len(s)
z = [0] * n
l = r = 0
for i in range(1, n):
if i <= r:
z[i] = min(r - i + 1, z[i - l])
while i + z[i] < n and s[z[i]] == s[i + z[i]]:
z[i] += 1
if i + z[i] - 1 > r:
l = i
r = i + z[i] - 1
return z
String Rolling Hash (Rabin–Karp)
class RH:
B = 911382323
M = 972663749 # example
def __init__(self, s: str):
n = len(s)
self.p = [1] * (n + 1)
self.h = [0] * (n + 1)
for i in range(n):
self.p[i + 1] = (self.p[i] * self.B) % self.M
self.h[i + 1] = (self.h[i] * self.B + ord(s[i])) % self.M
def get(self, l: int, r: int) -> int: # [l, r)
return (self.h[r] - self.h[l] * self.p[r - l]) % self.M