Formatted question description: https://leetcode.ca/all/1147.html
1147. Longest Chunked Palindrome Decomposition
Level
Hard
Description
Return the largest possible k
such that there exists a_1, a_2, ..., a_k
such that:
 Each
a_i
is a nonempty string;  Their concatenation
a_1 + a_2 + ... + a_k
is equal totext
;  For all
1 <= i <= k
,a_i = a_{k+1  i}
.
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:
text
consists only of lowercase English characters.1 <= text.length <= 1000
Solution
Use two pointers. Initially, low
and high
point to the minimum index and the maximum index of text
respectively. Also maintain the previous pointers prevLow
and prevHigh
, which are initially equal to low
and high
respectively.
Each time starting from low
, look for the first character that equals the character at high
. If such a character is found, loop in reversing order to find the longest chunk that can be covered. If the left side can be covered, increase the number of chunks by 2 and continue searching in a shorter substring. Otherwise, continue move the low
to the right to look for a character that equals the character at high
. Finally, if prevLow <= prevHigh
, then a new chunk is added at the middle. Finally, return the number of chunks.

class Solution { public int longestDecomposition(String text) { int chunks = 0; int low = 0, high = text.length()  1; int prevLow = low, prevHigh = high; int nextLow = 0; while (low < high) { while (low < high && text.charAt(low) != text.charAt(high)) low++; if (low == high) low; nextLow = low + 1; while (low >= prevLow) { if (text.charAt(low) == text.charAt(high)) { low; high; } else break; } if (low < prevLow) { chunks += 2; prevLow = nextLow; } else high = prevHigh; low = nextLow; prevHigh = high; } if (prevLow <= prevHigh) chunks++; return chunks; } }

// OJ: https://leetcode.com/problems/longestchunkedpalindromedecomposition/ // Time: O(N^2) // Space: O(1) class Solution { public: int longestDecomposition(string s) { int i = 0, N = s.size(), ans = 0; while (i < N / 2) { int len = 1; for (; i + len <= N / 2; ++len) { int j = 0; for (; j < len && s[i + j] == s[N  i  len + j]; ++j); if (j == len) break; // found match } if (i + len > N / 2) break; // match not found. ans += 2; i += len; } return ans + (i < (N + 1) / 2); } };

# 1147. Longest Chunked Palindrome Decomposition # https://leetcode.com/problems/longestchunkedpalindromedecomposition/ class Solution: def longestDecomposition(self, text: str) > int: n = len(text) res, l, r = 0, "", "" for a,b in zip(text, text[::1]): l, r = l + a, b + r if l == r: res, l, r = res + 1, "", "" return res