---

String Patterns – Optimized for Interview Prep

Strings are essentially character arrays, but unlike normal arrays, they introduce:

• Substrings vs subsequences
• Pattern matching
• Prefix/suffix logic
• Character frequency constraints
• Dictionary-based lookups
• Dynamic programming dependencies

The key to solving string problems efficiently is:

Identify the input structure → Notice the keywords → Map to the pattern → Apply optimal technique

Once you deeply internalize the keywords and structural triggers, you will instantly recognize which pattern to use.

---

How to Choose the Correct String Pattern

When the input structure is a string (or multiple strings), ask:

1. Is the problem about a contiguous substring?
2. Is it about a subsequence (not necessarily contiguous)?
3. Is it about matching a pattern inside a string?
4. Is it about counting characters or frequency constraints?
5. Is it about prefix search / dictionary lookup?
6. Is it about minimum edits / transformations between strings?
7. Is it about distinct characters or window constraints?

Each of these questions directly maps to a specific pattern below.

---

Pattern Table (Simplified & Prioritized – 4 Columns)

Pattern	Typical Question Types	Keywords / Detection Cues	Why Use / Notes
Sliding Window	Longest substring, Min window substring	substring, window	Expand/shrink window; O(n) optimal for contiguous problems.
Two Pointers	Palindrome, Reverse substring	left/right, reverse	Shrink/grow pointers from ends.
Trie	Autocomplete, Prefix search	prefix, dictionary	Tree-like structure for fast prefix lookup.
Hashing	Anagrams, Frequency count	frequency, count, anagram	Use hashmap/array for character counts.
KMP / Rabin-Karp	Exact pattern match	pattern, substring	Efficient O(n) pattern matching.
Z Algorithm (Bonus)	Pattern occurrences	prefix, substring	Linear-time prefix matching technique.
Rolling Hash (Bonus)	Substring matching	hash, substring	Compare substrings in O(1) after preprocessing.
DP on Strings	LCS, Edit distance, Palindrome subsequence	LCS, subsequence, match	Use 2D DP table for overlapping subproblems.
Sliding Window + Hashing	Distinct characters, substring constraints	window, unique, distinct	Maintain frequency map inside window.
Bitmask for Characters (Bonus)	Subset of characters, constraints	mask, subset, lowercase letters	Encode character presence using bits.

---

String Patterns – Full Detection & Mental Map

---

1. Sliding Window – Common (Strings & Arrays)

When to use:

• Input: Single string
• Looking for contiguous substring
• Optimizing brute force O(n²)

Keywords:

substring, window, longest, minimum, size k

Why it works:

You maintain a window [start → end] and expand/shrink depending on condition.

Typical Questions:

• Longest substring without repeating characters
• Minimum window substring
• Substring with at most K distinct characters

Mental Trigger:

“Contiguous substring” → Sliding Window

---

2. Two Pointers – Common

When to use:

• Checking symmetry
• Comparing characters from both ends

Keywords:

left/right, reverse, palindrome

Why it works:

Two pointers move inward to compare or modify.

Typical Questions:

• Valid palindrome
• Reverse string
• Palindrome after deleting one character

Mental Trigger:

“Compare ends” → Two Pointers

---

3. Trie – Common (Prefix Problems)

When to use:

• Multiple words
• Prefix search / dictionary lookup

Keywords:

prefix, dictionary, autocomplete

Why it works:

Trie stores characters in tree form → efficient prefix queries.

Typical Questions:

• Implement Trie
• Autocomplete system
• Word search dictionary

Mental Trigger:

“Prefix search” → Trie

---

4. Hashing – Common

When to use:

• Character frequency matters
• Order doesn’t matter

Keywords:

frequency, count, anagram

Why it works:

Store character counts using hashmap or fixed array (size 26).

Typical Questions:

• Valid anagram
• Group anagrams
• Ransom note

Mental Trigger:

“Count characters” → Hashing

---

5. KMP / Rabin-Karp – Common (Pattern Matching)

When to use:

• Find pattern inside string
• Avoid O(nm) brute force

Keywords:

pattern match, substring search

Why it works:

• KMP → Uses LPS array
• Rabin-Karp → Uses rolling hash

Both achieve near O(n).

Typical Questions:

• Find substring index
• Repeated pattern detection

Mental Trigger:

“Exact pattern search” → KMP / Rabin-Karp

---

6. Z Algorithm – Rare / Bonus

When to use:

• Need prefix match information for all indices

Keywords:

prefix match, substring occurrences

Why it works:

Computes longest prefix match at every position in O(n).

Typical Questions:

• Count pattern occurrences
• String border problems

Mental Trigger:

“Prefix matching at every index” → Z Algorithm

---

7. Rolling Hash – Rare / Bonus

When to use:

• Compare substrings quickly
• Repeated substring detection

Keywords:

hash, substring compare

Why it works:

Precompute polynomial hashes; compare in O(1).

Typical Questions:

• Longest duplicate substring
• Substring equality queries

Mental Trigger:

“Fast substring comparison” → Rolling Hash

---

8. DP on Strings – Common

When to use:

• Two strings involved
• Subsequence (not contiguous)
• Edit operations

Keywords:

LCS, subsequence, edit distance, match

Why it works:

Build 2D DP table using recurrence relation.

Typical Questions:

• Longest Common Subsequence
• Edit Distance
• Longest Palindromic Subsequence

Mental Trigger:

“Subsequence / transformations” → DP on Strings

---

9. Sliding Window + Hashing – Common

When to use:

• Substring with character constraints
• Need distinct count

Keywords:

unique, distinct, window

Why it works:

Maintain frequency map while expanding/shrinking window.

Typical Questions:

• Longest substring with K distinct characters
• Count substrings with exactly K distinct characters

Mental Trigger:

“Window + distinct constraint” → Sliding Window + Hashing

---

10. Bitmask for Characters – Rare / Bonus

When to use:

• Small fixed alphabet (usually lowercase letters)
• Need fast subset operations

Keywords:

mask, subset, bit representation

Why it works:

Use integer bits to represent character presence.

Typical Questions:

• Maximum product of word lengths
• Unique character combinations

Mental Trigger:

“Small alphabet + subset logic” → Bitmask

---

Mini Notes / Tips

### Tips

- First decide: substring (contiguous) or subsequence (non-contiguous)?
- Substring + optimization → Sliding Window.
- Subsequence + two strings → DP.
- Character counting → Hashing.
- Prefix search → Trie.
- Exact pattern match → KMP / Rolling Hash.
- Unique/distinct constraint → Sliding Window + Hashing.
- Small alphabet constraints → Bitmask.
- Always map: Input structure → Keywords → Pattern.