Blind 75 — String Pattern Guide

How to Identify a “String” Problem

Interview Triggers

• Input is a String or char[]
• “Substring” / “subsequence” / “palindrome” / “anagram”
• “Sliding window” of characters
• “Group” or “match” strings
• Encoding / decoding / parsing
• “Valid parentheses” / matching brackets

Which Sub-Pattern Does It Belong To?

If the prompt says…	Use this sub-pattern	Example LC
Longest substring with no repeating chars	Sliding window + Set/Map	3
Longest substring after K replacements	Sliding window + most frequent	424
Smallest substring containing all chars of T	Sliding window + freq map	76
Are two strings anagrams?	Frequency count (array[26])	242
Group strings that are anagrams	Sorted key in HashMap	49
Valid open/close brackets	Stack matching	20
Palindrome check ignoring punctuation	Two pointers + skip	125
Longest palindromic substring	Expand around center	5
Count all palindromic substrings	Expand around center	647
Encode/decode list of strings	Length-delimited format	271

---

The Decision Tree

STRING PROBLEM
│
├─ Contiguous window with a constraint?
│   └─ Sliding window
│       ├─ Distinct chars     → set/map (LC 3)
│       ├─ K changes allowed  → freq map + maxFreq (LC 424)
│       └─ All of T present   → freq map + matched count (LC 76)
│
├─ Anagram-related?
│   ├─ Check equality          → freq array[26] (LC 242)
│   └─ Group anagrams          → sorted key map (LC 49)
│
├─ Palindrome?
│   ├─ Check whole string      → two pointers (LC 125)
│   ├─ Longest substring       → expand around center (LC 5)
│   └─ Count substrings        → expand around center (LC 647)
│
├─ Matching brackets / nesting?
│   └─ Stack (LC 20)
│
└─ Serialization between client & server?
    └─ Length-delimited encoding (LC 271)

---

The Sliding Window Template (Variable Size)

int left = 0, best = 0;
Map<Character, Integer> freq = new HashMap<>();
for (int right = 0; right < s.length(); right++) {
    freq.merge(s.charAt(right), 1, Integer::sum);
    while (windowInvalid(freq)) {                    // contract from left
        freq.merge(s.charAt(left), -1, Integer::sum);
        if (freq.get(s.charAt(left)) == 0) freq.remove(s.charAt(left));
        left++;
    }
    best = Math.max(best, right - left + 1);
}
return best;

The Expand-Around-Center Template (Palindrome)

int start = 0, maxLen = 0;
for (int i = 0; i < s.length(); i++) {
    int len1 = expand(s, i, i);       // odd length
    int len2 = expand(s, i, i + 1);   // even length
    int len = Math.max(len1, len2);
    if (len > maxLen) { start = i - (len - 1) / 2; maxLen = len; }
}
int expand(String s, int l, int r) {
    while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) { l--; r++; }
    return r - l - 1;
}

---

Bread & Butter Problems

#	Problem	LC #	Difficulty	Sub-Pattern
1	Valid Anagram	242	Easy	freq array[26]
2	Valid Palindrome	125	Easy	Two pointers + skip
3	Valid Parentheses	20	Easy	Stack matching
4	Group Anagrams	49	Medium	Sorted key map
5	Longest Substring Without Repeating	3	Medium	Sliding window

FAANG “Aha!” Problems

#	Problem	LC #	Difficulty	Sub-Pattern
1	Longest Repeating Character Replacement	424	Medium	Sliding window
2	Minimum Window Substring	76	Hard	Sliding window
3	Longest Palindromic Substring	5	Medium	Expand around center
4	Palindromic Substrings	647	Medium	Expand around center
5	Encode and Decode Strings	271	Medium	Length-delimited

---

Java Implementation Tips

• For ASCII-only input, use int[26] over HashMap<Character,Integer> — 10× faster, simpler.
• Don’t repeat s.charAt(i) calls — cache to a local char c when used 3+ times.
• For “group anagrams”, sort key is simplest (O(K log K)); freq-of-26 key is faster but uglier.
• Character.isLetterOrDigit(c) + Character.toLowerCase(c) keep palindrome code clean (LC 125).
• For stack of chars, prefer ArrayDeque<Character> over Stack (legacy, synchronized).

---

Senior Mental Trigger

“Contiguous + constraint → sliding window. Palindrome → expand from center. Anagram → frequency count.”