#1147
Longest Chunked Palindrome Decomposition
expert · 1205 · lc hard +32 · verified · 59% accepted · 710 likes · top 56%
Description
You are given a string text. Partition it into k substrings (subtext1, subtext2, ..., subtextk) satisfying all of the following:
- Each subtexti is non-empty.
- Joining all substrings in order reconstructs text (i.e., subtext1 + subtext2 + ... + subtextk == text).
- The partition forms a palindrome arrangement: subtexti == subtextk - i + 1 for every valid i (i.e., 1 <= i <= k).
Return the maximum achievable value of k.
Example 1:
Input: text = "ghiabcdefhelloadamhelloabcdefghi"
Output: 7
Explanation: We can split the string on "(ghi)(abcdef)(hello)(adam)(hello)(abcdef)(ghi)".
Example 2:
Input: text = "merchant"
Output: 1
Explanation: We can split the string on "(merchant)".
Example 3:
Input: text = "antaprezatepzapreanta"
Output: 11
Explanation: We can split the string on "(a)(nt)(a)(pre)(za)(tep)(za)(pre)(a)(nt)(a)".
Code
1
2
3