# 1147. Longest Chunked Palindrome Decomposition

You are given a string `text`. You should split it to k substrings `(subtext1, subtext2, ..., subtextk)` such that:

• `subtexti` is a non-empty string.
• The concatenation of all the substrings is equal to `text` (i.e., `subtext1 + subtext2 + ... + subtextk == text`).
• `subtexti == subtextk - i + 1` for all valid values of `i` (i.e., `1 <= i <= k`).

Return the largest possible 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)(tpe)(za)(pre)(a)(nt)(a)".
``````

Example 4:

``````Input: text = "aaa"
Output: 3
Explanation: We can split the string on "(a)(a)(a)".
``````

Constraints:

• `1 <= text.length <= 1000`
• `text` consists only of lowercase English characters.

``````class Solution {
public:
int longestDecomposition(string text) {
int res = 0, n = text.size();
string left, right;
for (int i = 0; i < n; ++i) {
left += text[i], right = text[n - i - 1] + right;
if (left == right) {
++res;
left = right = "";
}
}
return res;
}
};
``````

``````class Solution {
public:
int longestDecomposition(string text) {
int n = text.size();
for (int i = 1; i <= n / 2; ++i) {
if (text[0] == text[n - i] && text[i - 1] == text[n - 1]) {
if (text.substr(0, i) == text.substr(n - i)) {
return 2 + longestDecomposition(text.substr(i, n - 2 * i));
}
}
}
return n == 0 ? 0 : 1;
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1147

https://leetcode.com/problems/longest-chunked-palindrome-decomposition/

https://leetcode.com/problems/longest-chunked-palindrome-decomposition/discuss/350560/JavaC%2B%2BPython-Easy-Greedy-with-Prove

https://leetcode.com/problems/longest-chunked-palindrome-decomposition/discuss/350762/Java-0ms-concise-beats-100-(both-time-and-memory)-with-algo

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation