menu_bookGyanByte
Practice SetLesson 251 min read

String Algorithms — Practice Problems

November 05, 2026

// How to use this set

Work these in order: easy (strStr, Repeated Substring Pattern) → medium (Repeated DNA Sequences, Repeated String Match, Encode and Decode Strings, Palindromic Substrings, Reverse Words in a String) → hard (Shortest Palindrome, Longest Happy Prefix, Longest Duplicate Substring). The easy ones drill the prefix-function idea; the hard ones combine KMP or Rabin-Karp with binary search. Cover the approach, solve it yourself, then check the code. Every solution below was run and tested.

Ten problems that drill KMP’s prefix function and Rabin-Karp’s rolling hash from Lesson 25. These are the hard end of string questions — read the approach, try it yourself, then check the tested code.

How to practise. For each problem, first decide which tool fits: is this about the pattern’s own structure (borders, periods → KMP’s prefix function) or about comparing many windows by content (→ rolling hash)? Implement the prefix function from memory at least once — it is the single most reusable piece of code here. If you stall for more than ~25 minutes on a hard one, read the approach, then re-solve it from scratch the next day.

The 10 problems

  1. 1Find the Index of the First Occurrence in a String (LeetCode 28)EasyFind where needle first appears in haystack: KMP's prefix table lets the scan never move backwards.arrow_forward
  2. 2Repeated Substring Pattern (LeetCode 459)EasyIs a string some block repeated? It is exactly when s appears inside (s + s) with both ends trimmed.arrow_forward
  3. 3Repeated DNA Sequences (LeetCode 187)MediumFind every 10-letter DNA substring that occurs more than once: slide a window and track seen windows in a set.arrow_forward
  4. 4Repeated String Match (LeetCode 686)MediumFewest copies of a so that b is a substring: repeat until long enough, then at most one extra copy.arrow_forward
  5. 5Encode and Decode Strings (LeetCode 271)MediumPack a list of strings into one string and back: prefix each with its length and a '#', never scan content.arrow_forward
  6. 6Palindromic Substrings (LeetCode 647)MediumCount all palindromic substrings: expand outwards from each of the 2n − 1 centres, one count per step.arrow_forward
  7. 7Reverse Words in a String (LeetCode 151)MediumReverse the order of words and normalise spaces: split on whitespace, reverse, join with single spaces.arrow_forward
  8. 8Shortest Palindrome (LeetCode 214)HardPrepend fewest chars to make a palindrome: KMP on s + '#' + reverse(s) finds the longest palindromic prefix.arrow_forward
  9. 9Longest Happy Prefix (LeetCode 1392)HardLongest proper prefix that is also a suffix: build the KMP prefix function and read its last value.arrow_forward
  10. 10Longest Duplicate Substring (LeetCode 1044)HardLongest substring that appears twice: binary-search its length, and check each length with a rolling hash.arrow_forward
coding-interviewstringskmprabin-karpleetcodepythonpractice
arrow_back Back to the lessonString Algorithms: KMP & Rabin-KarpNext lesson arrow_forwardMath & Geometry