In this guide, you will get 1147. Longest Chunked Palindrome Decomposition LeetCode Solution with the best time and space complexity. The solution to Longest Chunked Palindrome Decomposition problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of 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)(tep)(za)(pre)(a)(nt)(a)”.
Constraints:
1 <= text.length <= 1000
text consists only of lowercase English characters.
Complexity Analysis
Time Complexity: O(n^2)
Space Complexity: O(n)
1147. Longest Chunked Palindrome Decomposition LeetCode Solution in C++
class Solution {
public:
int longestDecomposition(string text) {
int count = 0;
int l = 0;
for (int r = 1; 2 * r <= text.length(); ++r)
if (equal(text.begin() + l, text.begin() + r, text.end() - r)) {
count += 2;
l = r;
}
return count + (2 * l < text.length());
}
}; /* code provided by PROGIEZ */
1147. Longest Chunked Palindrome Decomposition LeetCode Solution in Java
class Solution {
public int longestDecomposition(String text) {
final int n = text.length();
int count = 0;
int l = 0;
for (int r = 1; 2 * r <= n; ++r)
if (text.substring(n - r).startsWith(text.substring(l, r))) {
count += 2;
l = r;
}
return count + (2 * l < n ? 1 : 0);
}
} // code provided by PROGIEZ
1147. Longest Chunked Palindrome Decomposition LeetCode Solution in Python
