Disjoint Long Palindromes

Hard

You are given a string text and a positive integer min_len. Choose several non-overlapping substrings (contiguous pieces) of the string so that each one is a palindrome, reading the same forwards and backwards, and has length at least min_len. Return the largest number of substrings you can choose.

Example 1

text="levelxnoonyy", min_len=3 → 2

"level" and "noon" work: both are palindromes of length at least 3 and they do not overlap. "yy" is too short.

Example 2

text="aaaa", min_len=2 → 2

The string splits into "aa" and "aa".

Example 3

text="abcd", min_len=2 → 0

Constraints

1 ≤ min_len ≤ len(text) ≤ 2000
text consists of lowercase English letters

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Two Pointers String Dynamic Programming

Similar problems

Mirror Chunk Split Hard Nearly Matching Picks Medium Does the Text Fit the Pattern Hard Two Lines With Transfer Stops Hard Palindrome by Adjacent Swaps Hard

Input

text="levelxnoonyy", min_len=3

Expected

Run checks the first 3 tests in your browser. Submit checks all 111 tests on the server, hidden ones included.