Synthesis: which pattern to use?
Five patterns covered. Time to train the reflex that earns the interview: read a new string prompt and know which tool to reach for — with justification.
The section's decision tree
1. Does the ORDER of the characters NOT matter, only the composition?
├── Compare/group whole strings by composition
│ → FREQUENCY COUNTING (anagrams)
└── Continue ↓
2. Is the answer a contiguous SUBSTRING that grows/shrinks under a condition?
→ SLIDING WINDOW with a frequency map
(no repeats / ≤ k swaps / covers a target)
3. Is the problem about SYMMETRY (palindrome)?
├── "Is this a palindrome?" → converging TWO POINTERS
└── "How many / the longest?" → EXPAND FROM THE CENTER (odd and even)
4. Is there NESTING or matching of openings/closings? Or "last pending"?
→ STACK (LIFO)
5. Do I need to REPRESENT data in a string and recover it without ambiguity?
→ length-prefix ENCODING (design)
And the usual sanity check: the limits. Remember that enumerating all substrings is already O(n²) — if n is large, that's almost never the way.
The section's complete map
| Pattern | Key question | Structure | Time | Space |
|---|---|---|---|---|
| Frequency (anagrams) | "same composition?" | count map | O(n) or O(n·k log k) | O(1)* |
| Sliding window | "substring that satisfies X?" | window + map | O(n) | O(1)* |
| Two pointers | "is it a palindrome?" | two indices from the ends | O(n) | O(1) |
| Expand from the center | "how many/longest palindrome?" | two indices from the center | O(n²) | O(1) |
| Stack | "nesting / last pending?" | LIFO stack | O(n) | O(n) |
| Encoding | "represent without ambiguity?" | length-prefix | O(n) | O(n) |
* O(1) when the alphabet is fixed (e.g.: 26 letters); otherwise O(min(n, alphabet)).
And the connection to the previous section, worth internalizing: frequency is the hash map, and sliding window and two pointers came from Array. You didn't learn 5 new tools — you learned to apply the Array ones to characters and got the stack, expand-from-the-center, and encoding as a bonus.
Section quiz
Prompts you haven't seen in the lessons. Identify the pattern and be able to say why. 7+ correct: ready for the exam.
🧠 Section quiz: String
0/81. 'Check whether s2 contains any permutation of s1 as a substring.' Which pattern?
2. 'Given a string, what's the length of the longest substring with at most 2 distinct characters?' Which pattern?
3. 'How many palindromic substrings are there in s?' Which pattern and what complexity?
4. 'Remove all invalid parentheses to make the expression valid.' What structure is the natural basis?
5. 'Is it a palindrome if you can remove at most one character?' Which pattern?
6. 'Encode a binary tree into a string and reconstruct it.' Which String-section principle applies?
7. 'Are s and t anagrams?' — why NOT use a sliding window here?
8. What's the core idea that ties the String section to the Array section?
Ready for the exam?
The String section's final exam has three novel problems — easy, medium, and hard — with hidden cases. The five lessons cover everything you need, and the decision tree above settles the pattern choice for all three.
Good luck! Go back to the section page and click "Final exam".