# 1147.longest-chunked-palindrome-decomposition-cn

## 题目地址

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

## 题目描述

``````Return the largest possible k such that there exists a_1, a_2, ..., a_k such that:

Each a_i is a non-empty string;
Their concatenation a_1 + a_2 + ... + a_k is equal to text;
For all 1 <= i <= k,  a_i = a_{k+1 - i}.

Example 1:

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:

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

## 思路

### 复杂度分析

• 时间复杂度: `O(N^2) - N is the s length, s.substring()时间复杂度是O(n)`

• 空间复杂度: `O(1) - 没有额外的空间`

## 关键点分析

1. 回文，从左到右和从右到左是一样的字符串。那么分别从左和右扫描字符串，每次遇到左右相同，则`+2`, 如果最后没有剩余字符串，则返回结果。如果最后有剩余字符或字符串，则返回结果`+1`

2. 递归解类似, 同时左右对比.

## 代码 (`Java/Python3`)

### 解法一

Java code

``````class LongestChunkedPalindromeDecomp {
public int longestDecomposition2(String text) {
if (text == null || text.length() == 0) return 0;
int l = 0;
int r = text.length() - 1;
int max = 0;
int preL = l;
int preR = r;
while (l < r) {
// prefix include right [preL, l]
String prefix = text.substring(preL, l + 1);
// suffix include right [r, preR]
String suffix = text.substring(r, preR + 1);
if (prefix.equals(suffix)) {
preL = l + 1;
preR = r - 1;
max += 2;
}
l++;
r--;
}
// check whether any string left, if so, max+1
if (preL <= preR) max++;
return max;
}
}``````

Python3 code

``````class Solution:
def longestDecomposition(self, text: str) -> int:
n = len(text)
max, l, pre_l, r, pre_r = 0, 0, 0, n - 1, n - 1

while l < r:
if text[pre_l:l + 1] == text[r:pre_r + 1]:
pre_l = l + 1
pre_r = r - 1
max += 2
l += 1
r -= 1
if pre_l <= pre_r:
max += 1
return max``````

### 解法二 - 递归

Java code

``````class LongestChunkedPalindromDecom {
public int longestDecomposition1(String text) {
if (text == null || text.length() == 0) return 0;
int len = text.length();
for (int i = 0; i < len / 2; i++) {
String prefix = text.substring(0, i + 1);
String suffix = text.substring(len - i - 1, len);
if (prefix.equals(suffix)) {
return 2 + longestDecomposition1(text.substring(i + 1, len - i - 1));
}
}
return 1;
}
}``````

Python3 code

``````class Solution:
def longestDecomposition(self, text: str) -> int:
n = len(text)
if not text or n == 0:
return 0
for i in range(n // 2):
if text[0:i+1] == text[n - 1 - i:n]:
return 2 + self.longestDecomposition(text[i+1:(n - 1 - i)])
return 1``````

Last updated