DSA INTERVIEW PREP · STRING PATTERNS

ALL 15 PATTERNS

String
DSA
COMPLETE GUIDE
All 15 String patterns — sliding window, two
pointers, hashing, DP, KMP, Z-algo & more.

EXAMPLE STRING — used across all 15 patterns

Sliding window — longest no-repeat:

a b c a b c b b
0 1 2 3 4 5 6 7

Two pointers — palindrome check:

r a c e c a r
0 1 2 3 4 5 6

Pink=window Orange=bracket Cyan=matched

15 60+ O(n) 100%

Patterns LeetCode Qs Most Solutions Interview Ready

ALL 15 PATTERNS:
[Link] Pointers [Link] Window [Link] Map/Set [Link] [Link]

[Link] [Link] DP [Link] Match [Link] Algorithm 10.Z-Algorithm

[Link]-Karp [Link] [Link] Parsing [Link] [Link] Manip

■ ■ ■
String Diagrams Step-by-Step LeetCode Mapped
Visual char-by-char Full algorithm Top 4 problems
with pointers walkthrough per pattern

String DSA — All 15 Patterns [Link] · [Link] · [Link]

 PATTERN 1: TWO POINTERS 1

Two Pointers
Two Pointers place one pointer at each end and move inward, or use slow/fast pointers. Solves
palindrome, reverse, and matching problems in O(n) with O(1) space.

KEY RULE: while lo < hi: compare s[lo] and s[hi]; lo++; hi--

Classic: lo=0, hi=len-1. Compare s[lo] and s[hi].

Move both inward. For reverse: swap s[lo] and s[hi]. r a c e c a r
For palindrome: return False if mismatch. Also used 0 1 2 3 4 5 6

to remove duplicates or match two strings

simultaneously.
pink=outer pair cyan=inner pair orange=middle pair

WHEN TO USE

Palindrome check Reverse string in-place Remove chars matching condition Two-string comparison
APPROACH / ALGORITHM

1 Init: lo=0, hi=len(s)-1.

2 Loop while lo < hi: compare or process s[lo] and s[hi].
3 Palindrome: if s[lo]!=s[hi]: return False. lo++; hi--.
4 Reverse: s[lo],s[hi]=s[hi],s[lo]. lo++; hi--.
5 Skip chars: advance lo/hi past non-alphanumeric chars before comparing.

TOP LEETCODE QUESTIONS

Valid Palindrome LC 125

Reverse String LC 344

Valid Palindrome II LC 680

Reverse Vowels of String LC 345

Takeaway: Two pointers on strings = O(n) time, O(1) space — try this before any other approach.

String DSA 15 Patterns · Interview Prep

 PATTERN 2: SLIDING WINDOW 2

Sliding Window
Sliding Window maintains a valid substring between two pointers. Expand right to include chars,
shrink left when constraint violated. O(n) time.

KEY RULE: while freq[s[r]] > 1: freq[s[l]]-=1; l++ (shrink until valid)

Dynamic window: r expands always; l shrinks when

constraint broken. Use a hashmap to track char a b c a b c b b
counts in window. Fixed window: move both 0 1 2 3 4 5 6 7

pointers together. Classic problems: longest l r

no-repeat, minimum window substring. orange bracket=window [0..2]='abc' l=pink r=cyan

WHEN TO USE

Longest substring without repeat Minimum window substring Longest repeating after k replacements Fruits into baskets
APPROACH / ALGORITHM

1 Init: l=0; freq={}; best=0.

2 Expand right: for r in range(len(s)): freq[s[r]]+=1.
3 Shrink left: while constraint violated: freq[s[l]]-=1; if freq[s[l]]==0: del freq[s[l]]; l+=1.
4 Update: best=max(best, r-l+1).
5 Min window: shrink only when all required chars covered; track minimum length.

TOP LEETCODE QUESTIONS

Longest Substring Without Repeat LC 3

Minimum Window Substring LC 76

Longest Repeating Char Replace LC 424

Permutation in String LC 567

Takeaway: Shrink condition defines the window invariant — write it as a single boolean check.

String DSA 15 Patterns · Interview Prep

 PATTERN 3: HASH MAP / FREQUENCY COUNT 3

Hash Map & Frequency

Hash Map / Frequency Count stores character counts or indices for O(1) lookup. Essential for
anagram detection, first unique char, and substring problems.

KEY RULE: Counter(s) == Counter(t) → anagram | freq[ch]+=1 for ch in s

Anagram: count chars in both strings — all counts

must be zero. First unique: single-pass count then a n a g r a m
find first with count==1. Substring search: sliding 0 1 2 3 4 5 6

window + frequency map comparison. n a g a r a m

0 1 2 3 4 5 6

green dashes=matching chars between anagram pair

WHEN TO USE

Anagram detection First non-repeating char Ransom note / coverage Group all anagrams
APPROACH / ALGORITHM

1 Anagram: return sorted(s)==sorted(t) OR Counter(s)==Counter(t).

2 Sliding anagram: maintain freq window of size len(p); compare to target freq.
3 First unique: freq=Counter(s); for ch in s: if freq[ch]==1: return ch.
4 Ransom note: magazine must cover all chars in note — check counts.
5 Group anagrams: key=tuple(sorted(word)); group by key in defaultdict.

TOP LEETCODE QUESTIONS

Valid Anagram LC 242

First Unique Character LC 387

Ransom Note LC 383

Group Anagrams LC 49

Takeaway: Character frequency maps solve most 'string comparison' problems in O(n).

String DSA 15 Patterns · Interview Prep

 PATTERN 4: SORTING-BASED STRING 4

Sort to Simplify
Sorting-based string techniques sort chars to find canonical forms, detect anagrams, or compare
strings structurally. O(n log n) but clean and simple.

KEY RULE: canonical_key = tuple(sorted(word)) → group anagrams by key

Anagram via sort: sorted(s)==sorted(t). Canonical

key for grouping: tuple(sorted(word)). l i s t e n
Lexicographic comparison: Python strings compare 0 1 2 3 4 5

lexicographically by default. Custom sort: sort s i l e n t

words by length then alphabetically. 0 1 2 3 4 5

sorted('listen')=eilnst == sorted('silent')=eilnst

sorted canonical form reveals hidden equality

WHEN TO USE

Detect anagrams O(n log n) Group anagrams by sorted key Largest number from digits Custom string ordering
APPROACH / ALGORITHM

1 Anagram: return sorted(s)==sorted(t). Simple and clean.

2 Group: from collections import defaultdict; groups=defaultdict(list); groups[tuple(sorted(w))].append(w).
3 Largest number: sort strings with key=lambda a: a*3 (to handle prefix cases); join reversed.
4 Reorder log files: stable sort — letter logs by content then identifier; digit logs maintain order.
5 Alien dictionary: topological sort on character ordering extracted from adjacent words.

TOP LEETCODE QUESTIONS

Group Anagrams LC 49

Largest Number LC 179

Reorder Data in Log Files LC 937

Alien Dictionary LC 269

Takeaway: Sort gives you a canonical form — equal canonical forms means structurally identical strings.

String DSA 15 Patterns · Interview Prep

STRING DSA · CHECKPOINT

Patterns 1–4 Done!

Foundation string patterns covered

Two Pointers
1 lo/hi inward, palindrome & reverse

Sliding Window
2 expand right, shrink left

Hash Map / Freq

3 char counts for anagram & unique

Sorting-based
4 canonical form via sorted key

Keep Going — More Patterns Below →

String DSA 15 Patterns · Interview Prep

 PATTERN 5: PALINDROME TECHNIQUES 5

Palindrome Techniques
Palindrome problems use expand-from-center (O(n²)), Manacher's algorithm (O(n)), or DP table.
Each string position and pair can be a palindrome center.

KEY RULE: expand(l,r): while l>=0 and r<n and s[l]==s[r]: l--; r++; return s[l+1:r]

Expand from center: for each index i, expand

outward while s[l]==s[r]. Track longest. Handle both b a b a d
odd (center=i) and even (center between i and i+1) 0 1 2 3 4

cases. Manacher's: O(n) using previously

Expand from center: 'aba' and 'bab' both valid
computed palindrome radii.
window=palindrome center; expand both sides

WHEN TO USE

Longest palindromic substring Count palindromic substrings Palindrome partitioning Min insertions for palindrome
APPROACH / ALGORITHM

1 Expand from center: for i in range(n): odd=expand(i,i); even=expand(i,i+1); update best.

2 Expand helper: while l>=0 and r<n and s[l]==s[r]: l-=1; r+=1. return r-l-1 (length).
3 DP table: isPalin[i][j]=True if s[i]==s[j] and isPalin[i+1][j-1].
4 Count: each call to expand adds palindrome_radius count.
5 Min insertions: n - LPS(s) where LPS=longest palindromic subsequence.

TOP LEETCODE QUESTIONS

Longest Palindromic Substring LC 5

Palindromic Substrings LC 647

Palindrome Partitioning LC 131

Minimum Insertions for Palindrome LC 1312

Takeaway: Expand from center is O(n²) but beats DP for readability — Manacher's is O(n) for
competitive.

String DSA 15 Patterns · Interview Prep

 PATTERN 6: ANAGRAM & PERMUTATION 6

Anagram & Permutation

Anagram/Permutation in substring uses a sliding window of fixed size equal to the pattern
length. Compare frequency maps of window vs pattern at each position.

KEY RULE: if window_freq == pattern_freq: found anagram at position l

Maintain a window of size len(pattern). Use

26-length array (or dict) for char counts. Slide: add c b a e b a f d
s[r], remove s[l]. Check: if window_freq == 0 1 2 3 4 5 6 7

pattern_freq: found. Optimise by tracking 'matches'

pattern='abc'; window[0..2]='cba'=anagram!
counter instead of full comparison.
orange bracket=fixed window matching pattern freq

WHEN TO USE

Find all anagram positions Permutation in string Scramble string detection Minimum window with all chars
APPROACH / ALGORITHM

1 Init: p_freq=Counter(p); w_freq=Counter(s[:len(p)]).

2 Check initial window: if w_freq==p_freq: [Link](0).
3 Slide: for i in range(len(p), len(s)): add s[i]; remove s[i-len(p)] (delete if 0).
4 Check each position: if w_freq==p_freq: [Link](i-len(p)+1).
5 Optimise with matches: track how many of 26 chars have matching counts.

TOP LEETCODE QUESTIONS

Find All Anagrams in String LC 438

Permutation in String LC 567

Minimum Window Substring LC 76

Scramble String LC 87

Takeaway: Fixed-window sliding with frequency comparison = O(n) permutation search.

String DSA 15 Patterns · Interview Prep

STRING DSA · CHECKPOINT

Patterns 5–6 Done!

Palindrome & Anagram patterns

Palindrome
5 Expand from center or Manacher's

Anagram / Permutation
6 Fixed sliding window + freq map

String DP
7 LCS, edit distance, word break — next

Keep Going — More Patterns Below →

String DSA 15 Patterns · Interview Prep

 PATTERN 7: STRING DP 7

String DP
String DP solves LCS, Edit Distance, Word Break, and palindrome partitioning. A 2D table where
dp[i][j] represents the answer for substrings s1[0..i] and s2[0..j].

KEY RULE: LCS: dp[i][j]=dp[i-1][j-1]+1 if match else max(dp[i-1][j],dp[i][j-1])

LCS: match → dp[i][j]=dp[i-1][j-1]+1; mismatch → B D C A

max(dp[i-1][j], dp[i][j-1]). Edit Distance: match →
0 0 0 0 0
carry dp[i-1][j-1]; mismatch → 1+min(replace,
delete, insert). Word Break: dp[i]=True if any j A 0 1 1 1 1
where dp[j] and s[j:i] in wordSet.
B 0 1 1 1 2

C 0 1 2 2 2
LCS('ABC','BDCA')=2; pink=answer

WHEN TO USE pink=LCS answer cell in 2D dp table

Longest common subsequence Edit/Levenshtein distance Word break possibility Interleaving strings
APPROACH / ALGORITHM

1 LCS init: dp[i][0]=dp[0][j]=0.

2 LCS fill: if s1[i-1]==s2[j-1]: dp[i][j]=dp[i-1][j-1]+1 else max(dp[i-1][j],dp[i][j-1]).
3 Edit init: dp[i][0]=i, dp[0][j]=j.
4 Edit fill: if match: dp[i][j]=dp[i-1][j-1]; else dp[i][j]=1+min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1]).
5 Word break: dp[0]=True; dp[i]=any(dp[j] and s[j:i] in wordSet for j in range(i)).

TOP LEETCODE QUESTIONS

Longest Common Subsequence LC 1143

Edit Distance LC 72

Word Break LC 139

Interleaving String LC 97

Takeaway: String DP = LCS template or Edit Distance template — recognise which one fits the problem.

String DSA 15 Patterns · Interview Prep

 PATTERN 8: STRING PATTERN MATCHING 8

Pattern Matching
Pattern Matching finds all occurrences of a pattern in a text. Naive O(n·m); KMP and Z-algo
achieve O(n+m). Robin-Karp uses rolling hash.

KEY RULE: naive: for i in range(n-m+1): if text[i:i+m]==pattern: found

Naive: try matching pattern at every text position.

Use Python built-in [Link]() or [Link]() for A A B A A C A A D
interviews unless O(n) is required. Rolling hash 0 1 2 3 4 5 6 7 8

(Rabin-Karp) avoids redundant comparisons using

pattern='AABA'; window slides right checking each pos
polynomial hashing.
orange bracket slides across text checking each position

WHEN TO USE

Find pattern in text (single) Find all occurrences Repeated substring pattern Shortest period of string
APPROACH / ALGORITHM

1 Naive: for i in range(n-m+1): if text[i:i+m]==pat: [Link](i).

2 Built-in: pos=[Link](pat); while pos!=-1: [Link](pos); pos=[Link](pat,pos+1).
3 Repeated pattern: (s+s)[1:-1].find(s)!=-1 — classic trick.
4 Rolling hash: hash(window)=(hash*base + new_char - old_char*base^m) % MOD.
5 Rehash collision: verify text[i:i+m]==pat when hash matches to handle false positives.

TOP LEETCODE QUESTIONS

Implement strStr() LC 28

Repeated Substring Pattern LC 459

Find All Anagrams in String LC 438

Shortest Palindrome LC 214

Takeaway: In interviews, Python [Link]() is O(n) average — use it unless explicitly asked for KMP.

String DSA 15 Patterns · Interview Prep

STRING DSA · CHECKPOINT

Patterns 7–8 Done!

String DP & Pattern Matching

String DP
7 LCS/Edit table, word break

Pattern Matching
8 Naive, built-in, rolling hash

KMP Algorithm
9 O(n+m) failure function — next

Keep Going — More Patterns Below →

String DSA 15 Patterns · Interview Prep

 PATTERN 9: KMP ALGORITHM 9

KMP Algorithm
Knuth-Morris-Pratt (KMP) finds pattern in text in O(n+m) using a failure function (LPS array). On
mismatch, skip characters already matched using the LPS table.

KEY RULE: on mismatch: j = lps[j-1] (don't restart; jump to longest matching prefix)

Build LPS (Longest Proper Prefix which is also

Suffix) for pattern in O(m). During search: on match A B A B C
advance both. On mismatch: jump using lps[j-1] — 0 1 2 3 4

don't restart from 0. This avoids reprocessing

Failure fn: [0,0,1,2,0]
characters already verified. On mismatch at pos 4, jump to lps[3]=2 (not start)

lps table=jump table; skip to lps[j-1] on mismatch

WHEN TO USE

Pattern search O(n+m) Count pattern occurrences Repeated string check Prefix-suffix overlap
APPROACH / ALGORITHM

1 Build LPS: lps=[0]*m; length=0; i=1. While i<m: if pat[i]==pat[length]: length++; lps[i]=length; i++.
2 On LPS mismatch: if length!=0: length=lps[length-1]. Else: lps[i]=0; i++.
3 KMP search: i=0(text), j=0(pattern). While i<n: if text[i]==pat[j]: i++; j++.
4 Found: if j==m: record match at i-j; j=lps[j-1].
5 Mismatch: if j!=0: j=lps[j-1]. Else: i++.

TOP LEETCODE QUESTIONS

Find the Index of First Occurrence LC 28

Repeated Substring Pattern LC 459

Shortest Palindrome (KMP) LC 214

String Matching in Array LC 1408

Takeaway: KMP = failure function lets you skip work already done. Building LPS is half the battle.

String DSA 15 Patterns · Interview Prep

 PATTERN 10: Z-ALGORITHM 10

Z- Algorithm
Z-Algorithm computes Z[i] = length of longest substring starting at i that matches a prefix of the
string. O(n) time. Used to find pattern occurrences by concatenating pat + '$' + text.

KEY RULE: Z[i]=length matching prefix at i | match when Z[i+m+1]>=m

Z[0]=len(s) by convention. For i>0: Z[i] is the

Z-value. Pattern search: build Z for pat+'$'+text. a a b x a a b x c
Where Z[i]>=len(pat), a match is found. Uses a 0 1 2 3 4 5 6 7 8

window [l,r] to avoid recomputing already matched

Z array: [9,1,0,0,4,1,0,0,1]
characters. Z[4]=4: s[4..7]='aabx' matches s[0..3]='aabx'

Z[4]=4: 4 chars starting at idx 4 match prefix

WHEN TO USE

Pattern search O(n+m) Find all pattern occurrences Longest repeated prefix String period detection
APPROACH / ALGORITHM

1 Build Z array: Z=[0]*n; l=r=0. For i in range(1,n):

2 Within window: if i<r: Z[i]=min(r-i, Z[i-l]).
3 Extend: while i+Z[i]<n and s[Z[i]]==s[i+Z[i]]: Z[i]+=1.
4 Update window: if i+Z[i]-1>r: l=i; r=i+Z[i]-1.
5 Pattern search: s=pat+'$'+text; build Z; find i where Z[i]>=len(pat) → match at i-m-1.

TOP LEETCODE QUESTIONS

Find the Index of First Occurrence LC 28

Longest Happy Prefix LC 1392

Count Occurrences of Anagram LC Var

Shortest Palindrome LC 214

Takeaway: Z-algorithm and KMP are interchangeable — Z-algo is often simpler to implement from
scratch.

String DSA 15 Patterns · Interview Prep

STRING DSA · CHECKPOINT

Patterns 9–10 Done!

KMP & Z-Algorithm

KMP
9 Failure fn = jump table on mismatch

Z-Algorithm
10 Z[i]=prefix match length at position i

Rabin-Karp
11 Rolling hash for O(n) average search — next

Keep Going — More Patterns Below →

String DSA 15 Patterns · Interview Prep

 PATTERN 11: RABIN-KARP (ROLLING HASH) 11

Rabin-Karp Rolling Hash

Rabin-Karp uses polynomial rolling hash to match pattern in O(n) average. Hash window slides in
O(1) by removing leftmost char and adding rightmost char.

KEY RULE: new_hash=(old_hash*base + ord(new) - ord(old)*base^m) % MOD

Hash function: h = (c0·b^(m-1) + c1·b^(m-2) + … +

cm-1) % MOD. Rolling: remove first char's a b r a c a d a b
contribution, shift, add new char. On hash match: 0 1 2 3 4 5 6 7 8

verify character by character to handle collisions.

hash(abra)=hash(pat)? → verify. Slide window.
Rolling: new_hash = (old*base + new - old*base^m) % MOD

hash of orange window slides right in O(1) each step

WHEN TO USE

Find pattern in text O(n) avg Find repeated DNA sequences Longest duplicate substring Detect plagiarism
APPROACH / ALGORITHM

1 Compute initial hash: for ch in pat: h=(h*base+ord(ch))%MOD.

2 Same for first window: h_text for text[0:m].
3 Compare: if h_pat==h_text: verify text[i:i+m]==pat.
4 Roll window: h_text=(h_text-ord(text[i])*pow(base,m-1,MOD))*base+ord(text[i+m])%MOD.
5 MOD choice: use large prime (e.g. 10^9+7) to minimize collisions.

TOP LEETCODE QUESTIONS

Implement strStr (Rabin-Karp) LC 28

Repeated DNA Sequences LC 187

Longest Duplicate Substring LC 1044

Distinct Echo Substrings LC 1316

Takeaway: Rolling hash = O(1) window update. Always verify on hash match to handle collisions.

String DSA 15 Patterns · Interview Prep

 PATTERN 12: TRIE FOR STRING PROBLEMS 12

Trie / Prefix Tree

Trie (Prefix Tree) enables O(L) insert/search/prefix-query for strings of length L. Each node holds
up to 26 children and an is_end flag.

KEY RULE: insert: for ch in word: node=[Link](ch, TrieNode())

Insert: traverse/create nodes per character; mark

is_end at last. Search: traverse; return is_end at root

last char. StartsWith: traverse; return True if all

chars found (no is_end check). Used for
a b
autocomplete, word dictionary, and word search II.

p t a y

WHEN TO USE
p e
Autocomplete / prefix search Word dictionary with wildcard Word search in grid (Trie+DFS) Replace words with root
pink=word end (app,ate) orange=root
APPROACH / ALGORITHM pink=word-end nodes; orange=root

1 TrieNode: [Link]={}; self.is_end=False.

Insert: node=root; for ch in word: if ch not in [Link]: [Link][ch]=TrieNode();
2 node=[Link][ch]; node.is_end=True.
Search: node=root; for ch in word: if ch not in [Link]: return False; node=[Link][ch]; return
3 node.is_end.
4 StartsWith: same as search but return True (no is_end check at end).
5 Wildcard '.': DFS all children when '.' encountered.

TOP LEETCODE QUESTIONS

Implement Trie LC 208

Add and Search Word (wildcard) LC 211

Word Search II LC 212

Replace Words LC 648

Takeaway: Trie is just a tree where each edge = one character. Visualise edges not nodes.

String DSA 15 Patterns · Interview Prep

STRING DSA · CHECKPOINT

Patterns 11–12 Done!

Rabin-Karp & Trie

Rabin-Karp
11 Rolling hash O(1) window update

Trie
12 Prefix tree, O(L) insert/search

String Parsing
13 Tokenize, evaluate, decode — next

Keep Going — More Patterns Below →

String DSA 15 Patterns · Interview Prep

 PATTERN 13: STRING PARSING & STACK 13

String Parsing
String Parsing uses a stack to handle nested structures — brackets, parentheses, operators.
Process left-to-right; push on open; pop and process on close.

KEY RULE: on '[': push (curr_string, curr_num) to stack | on ']': pop and repeat

Stack-based parsing: push open

brackets/operands; on close bracket pop and 3 [ a 2 [ b ] ]
process. Evaluate expression: use operator 0 1 2 3 4 5 6 7

precedence with two stacks (nums and ops).

Stack: '3[' → 'a' → '2[' → 'bb' → pop → 'abb' → pop → 'abbabbabb'
Decode strings: push (repeat_count, built_string)
on '[', pop and repeat on ']'.
orange=num pink=brackets cyan=chars green=inner

WHEN TO USE

Decode encoded string Valid parentheses Basic calculator Remove duplicate letters
APPROACH / ALGORITHM

1 Decode string: stack=[]; curr=''; num=0. For ch: digit→num; '['→push(curr,num),reset; ']'→pop and repeat.
2 Valid parens: stack=[]. '('/'{':'['→push. ')'/'}'/'}'→check stack top matches. Return stack empty.
3 Calculator: stack for values and operators. Handle precedence: * and / before + and -.
4 Remove duplicate letters: greedy + stack. Push if not seen; pop if char will appear again and top is larger.
5 Simplify path: split by '/'; process '..' by popping stack; join with '/'.

TOP LEETCODE QUESTIONS

Decode String LC 394

Valid Parentheses LC 20

Basic Calculator II LC 227

Remove Duplicate Letters LC 316

Takeaway: Stack = implicit recursion. Whenever you see nested brackets or need to undo, reach for a
stack.

String DSA 15 Patterns · Interview Prep

 PATTERN 14: REGEX / WILDCARD MATCHING 14

Regex / Wildcard DP
Regex/Wildcard DP — match string s against pattern p with '.' (any char) and '*' (zero or more of
preceding). Fill a 2D dp table comparing each char of s with each char of p.

KEY RULE: if p[j-1]=='*': dp[i][j]=dp[i][j-2] OR (match and dp[i-1][j])

dp[i][j]=True if s[0..i-1] matches p[0..j-1]. Char a *

match or '.': dp[i][j]=dp[i-1][j-1]. '*' means zero uses
T F T
(dp[i][j-2]) or one-more use (dp[i-1][j] if prev pattern
char matches). a F T T

a F F T
'aa' matches 'a*'=True (pink=answer)

T=match; pink=final answer; magenta=partial match

WHEN TO USE

Regex matching . and * Wildcard matching ? and * Word pattern matching Shell glob matching
APPROACH / ALGORITHM

1 Init: dp[0][0]=True; dp[0][j]=dp[0][j-2] if p[j-1]=='*'.

2 Char match: if p[j-1]==s[i-1] or p[j-1]=='.': dp[i][j]=dp[i-1][j-1].
3 Star zero use: dp[i][j] |= dp[i][j-2].
4 Star one+ use: if p[j-2]==s[i-1] or p[j-2]=='.': dp[i][j] |= dp[i-1][j].
5 Answer: dp[m][n].

TOP LEETCODE QUESTIONS

Regular Expression Matching LC 10

Wildcard Matching LC 44

Word Pattern LC 290

Is Subsequence LC 392

Takeaway: Star case: zero (dp[i][j-2]) or extend (dp[i-1][j]) — these two cover all cases.

String DSA 15 Patterns · Interview Prep

 PATTERN 15: STRING MANIPULATION 15

String Manipulation
String Manipulation covers in-place reversal, rotation, compression, and encoding. These test
your knowledge of string operations and two-pointer tricks.

KEY RULE: rotate check: goal in (s+s) | reverse words: [Link]()[::-1]

Reverse words: split by spaces, reverse list, join.

Or: reverse whole string then reverse each word t h e s k y i
in-place. Run-length encode: count consecutive 0 1 2 3 4 5 6 7 8

same chars. String rotation: (s+s).find(goal) != -1. start sp w sp w

Roman to int: iterate right-to-left; add or subtract

reverse words: split → reverse → join = 'blue is sky the'
based on order.

pink=spaces(separators) purple=word chars

WHEN TO USE

Reverse words in string String compression/encoding Check string rotation Roman numerals conversion
APPROACH / ALGORITHM

1 Reverse words: return ' '.join([Link]()[::-1]). Handles multiple spaces.

2 In-place reverse words: reverse entire string; then reverse each word between spaces.
3 Run-length encode: count=1; for i in 1..n: if same: count++ else: append char+count; reset.
4 String rotation: if len(s)!=len(goal): False. return goal in (s+s).
5 Roman to int: right-to-left; if val<prev: subtract; else add. Map each symbol.

TOP LEETCODE QUESTIONS

Reverse Words in String LC 151

String Compression LC 443

Rotate String LC 796

Roman to Integer LC 13

Takeaway: Many manipulation problems have O(n) one-liner solutions — know your language's string
API.

String DSA 15 Patterns · Interview Prep

 ALL 15 STRING PATTERNS COMPLETE!

You Can Now

Solve Any
String Problem
You have mastered all 15 String patterns — Two Pointers, Sliding Window, Hash
Map/Set, Sorting-based, Palindrome DP, Anagram techniques, String DP, Pattern
Matching, KMP, Z-Algorithm, Rabin-Karp, Trie, String Parsing, Regex DP, and String
Manipulation. Recognise the pattern, apply the template, crack the interview.

→ Save & Share This Sheet

[Link] · [Link] · [Link]

String DSA 15 Patterns · Interview Prep