Welcome to Subscribe On Youtube
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 non-empty 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/longest-chunked-palindrome-decomposition/ // 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); } };
-
class Solution: def longestDecomposition(self, text: str) -> int: n = len(text) if n < 2: return n for i in range(n // 2 + 1): if text[:i] == text[-i:]: return 2 + self.longestDecomposition(text[i:-i]) return 1 ############ # 1147. Longest Chunked Palindrome Decomposition # https://leetcode.com/problems/longest-chunked-palindrome-decomposition/ 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
-
func longestDecomposition(text string) int { n := len(text) if n < 2 { return n } for i := 1; i <= n>>1; i++ { if text[:i] == text[n-i:] { return 2 + longestDecomposition(text[i:n-i]) } } return 1 }
-
function longestDecomposition(text: string): number { const n: number = text.length; if (n < 2) { return n; } for (let i: number = 1; i <= n >> 1; i++) { if (text.slice(0, i) === text.slice(n - i)) { return 2 + longestDecomposition(text.slice(i, n - i)); } } return 1; }