String Mastery Ladder

What This Ladder Trains: String algorithms from basic hashing through pattern matching to suffix structures. You'll progress through polynomial hashing, KMP/Z-function, trie-based approaches, and suffix array applications. By the end, you should confidently choose between hashing, KMP, Z-function, and suffix arrays depending on the problem constraints.

Quick Revisit

• SKILL FOCUS: string algorithm mastery -- hashing, KMP, Z-function, suffix arrays
• DIFFICULTY: 1200--2000
• PROBLEMS: 10
• PREREQUISITE: Strings

---

Contents

• Pre-ladder diagnostic
• Which tool to use
• Warm-Up (1200-1500)
• Core (1500-1700)
• Advanced (1700-1900)
• How to Use This Ladder

---

Pre-ladder diagnostic

Before starting the problems, check that you can answer these without notes. If any answer is fuzzy, return to Chapter 5: Strings before climbing — the ladder will not build the foundation, only test it.

• Can you compute one Z-array by hand for a 6-character string?
• Can you state in one sentence what fail[i] means in KMP, and why it lets you avoid restarting on a mismatch?
• Given a string of length n, what does a suffix array let you do that hashing alone cannot?
• What is the cost of a single-hash collision in a competitive setting, and when do you need double hashing?

Which tool to use

The whole ladder is about choosing between hashing, KMP, Z, trie, and suffix arrays. Internalize this decision frame before the problem list, and use it as the first thing you ask on every problem:

• Need to check equality of arbitrary substrings, possibly many times → hashing.
• Need all positions where a fixed pattern occurs in a text → KMP.
• Need all prefix matches of a string against itself (or against a concatenation) → Z-function.
• Need prefix containment over a dynamic set of strings → trie.
• Need distinct substring counts, k-th substring, or LCP of suffixes → suffix array (with LCP).

Most failures in this ladder are not implementation bugs — they are choosing the wrong tool, then forcing it.

Basic string manipulation, hashing fundamentals, and trie introduction.

#	Problem	Rating	Hint
1	Substring Removal	1200	Hint Count valid strings by choosing a prefix of one character and a suffix of one character (possibly the same). Handle overlap carefully.
2	Good Substrings	1500	Hint Insert all substrings into a trie (or use hashing), counting bad characters along the way. A substring is good if bad count <= k.
3	Unstable String	1600	Hint For each position, track the longest alternating extension ending here for both parities. '?' extends both.

If you struggled here, review Chapter 5: Strings -- hashing basics and trie construction.

---

Core (1500-1700)

KMP failure function, Z-function, and pattern matching applications.

#	Problem	Rating	Hint
4	Password	1700	Hint Use the Z-function (or KMP failure array). Find the longest prefix that is also a suffix AND appears in the middle of the string.
5	Tavas and Malekas	1800	Hint Each marked position places pattern p. Check overlapping placements are consistent using KMP failure function or hashing.
6	Prefix-Suffix Palindrome	1800	Hint Match the longest prefix-suffix pair greedily. For the unmatched middle part, find the longest palindromic prefix or suffix (use hashing or Manacher).
7	Compress Words	2000	Hint When appending word w to result r, find the longest suffix of r that is a prefix of w using KMP on w + '#' + suffix_of_r.

If you struggled here, review Chapter 5: Strings -- KMP, Z-function, and string hashing sections.

---

Advanced (1700-1900)

Z-function mastery, suffix arrays, and combining string algorithms with DP.

#	Problem	Rating	Hint
8	Prefixes and Suffixes	2000	Hint Use the Z-function to find all prefix-suffixes. Count occurrences of each prefix using suffix sorting on Z-values.
9	Test	2000	Hint Find the shortest superstring of 3 given strings. Try all 6 orderings, using Z-function to compute max overlap between pairs.
10	Lucky Common Subsequence	2000	Hint LCS of two strings that avoids a third as a substring. DP with states (i, j, k) where k tracks the KMP automaton state of the forbidden pattern.

If you struggled here, review Chapter 5: Strings -- suffix arrays and advanced hashing -- and Chapter 4: Dynamic Programming for DP on strings.

---

How to Use This Ladder

1. Re-read the Which tool to use section above for every problem before coding. The wrong-tool failure mode is the dominant one in this ladder.
2. Implement Z-function and KMP from scratch before starting Core. If you can't write them in 10 minutes, practice until you can.
3. Time-box: 30 min for Warm-Up, 45 min for Core, 60-75 min for Advanced.
4. Compare approaches. Many problems here can be solved with either hashing or KMP/Z. After AC, try the alternative to internalize the tradeoffs.

Progression Check

• [ ] Warm-Up: solved all 3 without hints
• [ ] Core: solved >= 3/4 within time limits
• [ ] Advanced: attempted all 3, solved >= 1
• [ ] Can implement KMP and Z-function from memory
• [ ] Understand when to use hashing vs KMP vs suffix arrays

---

See also: Strings | Rating ladders | Mixed Ladder