Welcome to the String Processing template collection! These are ready-to-use C++ snippets for the core string patterns: sliding window, two pointers, string matching, manipulation, and parsing. If you already know the array templates, you’re most of the way there — strings use the same ideas with character-level twists. See also Arrays & Strings for KMP and rolling hash.
String problems are array problems in disguise. Most string patterns — sliding window, two pointers, prefix computation — work identically to their array counterparts. The main difference is that you operate on characters and often track frequencies with a hash map or fixed-size array.
Contents
Sliding Window
When to use: The problem asks for “longest substring without repeating characters”, “minimum window containing all characters”, or any contiguous substring optimization with a frequency constraint.
Minimum Window — s = "ADOBECODEBANC", t = "ABC"
Step 1: expand until valid
A
D
O
B
E
C
← window "BEC" has A,B,C ✓
Step 2: shrink from left
A
B
E
C
shrink left → "BEC" (len=3)
Pattern: expand right until valid → shrink left while still valid → track minimum length
left pointer ────────────────────────────── right pointer
Longest Substring Without Repeating Characters
def length_of_longest_substring ( s : str ) -> int :
cnt = [ 0 ] * 256
dup = 0
best = 0
l = 0
for r in range ( len ( s )):
idx = ord ( s [ r ]) % 256
cnt [ idx ] += 1
if cnt [ idx ] == 2 :
dup += 1
while dup > 0 :
j = ord ( s [ l ]) % 256
cnt [ j ] -= 1
if cnt [ j ] == 1 :
dup -= 1
l += 1
best = max ( best , r - l + 1 )
return best
Minimum Window Substring
def min_window ( s : str , t : str ) -> str :
from collections import Counter
need = Counter ( t )
window : dict [ str , int ] = {}
left = right = 0
valid = 0
start , min_len = 0 , 10 ** 9
while right < len ( s ):
c = s [ right ]
right += 1
if c in need :
window [ c ] = window . get ( c , 0 ) + 1
if window [ c ] == need [ c ]:
valid += 1
while valid == len ( need ):
if right - left < min_len :
start = left
min_len = right - left
d = s [ left ]
left += 1
if d in need :
if window [ d ] == need [ d ]:
valid -= 1
window [ d ] -= 1
return "" if min_len == 10 ** 9 else s [ start : start + min_len ]
ID
Title
Link
Solution
3
Longest Substring Without Repeating Characters
Link Solution
76
Minimum Window Substring
Link -
424
Longest Repeating Character Replacement
Link -
Two Pointers
When to use: The problem mentions “palindrome”, “reverse string”, or requires comparing characters from both ends of a string moving inward.
Valid Palindrome
def is_palindrome ( s : str ) -> bool :
left , right = 0 , len ( s ) - 1
while left < right :
while left < right and not s [ left ]. isalnum ():
left += 1
while left < right and not s [ right ]. isalnum ():
right -= 1
if s [ left ]. lower () != s [ right ]. lower ():
return False
left += 1
right -= 1
return True
Reverse String
def reverse_string_list ( s : list [ str ]) -> None :
left , right = 0 , len ( s ) - 1
while left < right :
s [ left ], s [ right ] = s [ right ], s [ left ]
left += 1
right -= 1
String Matching
When to use: The problem asks to “find a pattern in text”, mentions “KMP”, or requires efficient O(n+m) substring search instead of brute-force O(n·m).
KMP Algorithm
def build_kmp_lps ( pattern : str ) -> list [ int ]:
m = len ( pattern )
lps = [ 0 ] * m
length = 0
i = 1
while i < m :
if pattern [ i ] == pattern [ length ]:
length += 1
lps [ i ] = length
i += 1
else :
if length != 0 :
length = lps [ length - 1 ]
else :
lps [ i ] = 0
i += 1
return lps
def kmp_search ( text : str , pattern : str ) -> int :
n , m = len ( text ), len ( pattern )
if m == 0 :
return 0
lps = build_kmp_lps ( pattern )
i = j = 0
while i < n :
if text [ i ] == pattern [ j ]:
i += 1
j += 1
if j == m :
return i - j
if i < n and text [ i ] != pattern [ j ]:
if j != 0 :
j = lps [ j - 1 ]
else :
i += 1
return - 1
ID
Title
Link
Solution
28
Find the Index of the First Occurrence in a String
Link -
String Manipulation
When to use: The problem says “anagram”, “group anagrams”, “remove duplicates”, or requires rearranging or classifying strings by their character composition.
Group Anagrams
from collections import defaultdict
def group_anagrams ( strs : list [ str ]) -> list [ list [ str ]]:
groups : dict [ tuple [ str , ...], list [ str ]] = defaultdict ( list )
for w in strs :
key = tuple ( sorted ( w ))
groups [ key ]. append ( w )
return list ( groups . values ())
Remove Duplicates
# Remove All Adjacent Duplicates
def remove_adjacent_duplicates ( s : str ) -> str :
st : list [ str ] = []
for c in s :
if st and st [ - 1 ] == c :
st . pop ()
else :
st . append ( c )
return "" . join ( st )
# Remove All Adjacent Duplicates II (k duplicates)
def remove_adjacent_duplicates_k ( s : str , k : int ) -> str :
st : list [ list ] = [] # [char, count]
for c in s :
if st and st [ - 1 ][ 0 ] == c :
st [ - 1 ][ 1 ] += 1
if st [ - 1 ][ 1 ] == k :
st . pop ()
else :
st . append ([ c , 1 ])
return "" . join ( ch * cnt for ch , cnt in st )
Run-Length Encoding
# Two-pointer grouping for consecutive runs (illustrative RLE)
def run_length_encode ( s : str ) -> str :
parts : list [ str ] = []
j = 0
n = len ( s )
while j < n :
k = j
while k < n and s [ k ] == s [ j ]:
k += 1
parts . append ( str ( k - j ) + s [ j ])
j = k
return "" . join ( parts )
ID
Title
Link
Solution
38
Count and Say
Link Solution
443
String Compression
Link -
Parsing
When to use: The problem says “decode string”, “valid abbreviation”, “nested brackets”, or requires interpreting a string according to grammar rules.
Valid Word Abbreviation
def valid_word_abbreviation ( word : str , abbr : str ) -> bool :
i = j = 0
n , m = len ( word ), len ( abbr )
while i < n and j < m :
if abbr [ j ]. isdigit ():
if abbr [ j ] == "0" :
return False
num = 0
while j < m and abbr [ j ]. isdigit ():
num = num * 10 + int ( abbr [ j ])
j += 1
i += num
else :
if word [ i ] != abbr [ j ]:
return False
i += 1
j += 1
return i == n and j == m
Decode String
def decode_string ( s : str ) -> str :
num_stack : list [ int ] = []
str_stack : list [ str ] = []
current = ""
num = 0
for c in s :
if c . isdigit ():
num = num * 10 + int ( c )
elif c == "[" :
num_stack . append ( num )
str_stack . append ( current )
num = 0
current = ""
elif c == "]" :
repeat = num_stack . pop ()
prev = str_stack . pop ()
current = prev + current * repeat
else :
current += c
return current
Summary
Pattern
Signal Phrases
Key Idea
Sliding Window
“longest substring”, “minimum window”
Track char frequencies in window
Two Pointers
“palindrome”, “reverse”
Compare from both ends
String Matching
“pattern in text”, “KMP”
Failure function for O(n+m)
Manipulation
“anagram”, “group anagrams”
Sort or frequency count
Parsing
“decode string”, “nested brackets”
Stack-based recursion
More templates