HardDpAI interview only
Maximum Number of Non-Overlapping Palindrome Substrings
Asked atgoogleamazonmeta
01 · Problem
You are given a string s of lowercase English letters and a positive integer k. Choose a set of substrings of s such that:
- every chosen substring has length at least
k, - every chosen substring is a palindrome (reads the same forwards and backwards), and
- no two chosen substrings overlap (they share no index).
Return the maximum number of substrings you can choose. Return 0 if no valid substring exists.
02 · Examples
Example 01
Input
s = "abaccdbbd", k = 3
Output
2
Choose "aba" (indices 0-2) and "dbbd" (indices 5-8). Both are palindromes of length at least 3 and they do not overlap.
Example 02
Input
s = "adbcda", k = 2
Output
0
No substring of length 2 or more is a palindrome.
03 · Constraints
- 011 <= s.length <= 2000
- 021 <= k <= s.length
- 03s consists of lowercase English letters
04 · Optimal complexity
- Time
- O(n * k)
- Space
- O(n)
05 · Two ways to work on it
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.