Last Updated: 2 Apr, 2021

Longest Chunked Palindrome Decomposition

Moderate

Asked in company

Problem statement

You are given a string ‘S’. Your task is to find the length of it’s longest possible chunked palindrome. In other words, you have to split the string ‘S’ into ‘K’ substrings ((Sub)1, (Sub)2, (Sub)3, ..., (Sub)K) such that:

1. The substring ‘(Sub)i’ is a non-empty string, for all 1 <= i <= K.
2. (Sub)1 + (Sub)2 + (Sub)3 + … + (Sub)K = ‘S’, which means the concatenation of all the substrings is equal to ‘S’.
3. (Sub)i = (Sub)(K-i+1), for all 1 <= i <= ‘K’.

You have to find the largest possible value of ‘K’

Note :

1. The string ‘S’ consists of only lowercase English alphabets.
2. A ‘substring’ is a contiguous sequence of characters within a string.

Input Format :

The first line contains an integer ‘T’, which denotes the number of test cases to be run. Then, the ‘T’ test cases follow. 

The first and only line of each test case contains a string ‘S’ of lowercase English alphabets.

Output Format :

For each test case, print in a new line an integer denoting the length of the longest possible chunked palindrome of string ‘S’.

Output for each test case will be printed in a separate line.

Note :

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 10
1 <= |S| <= 1000

where 'T' denotes the number of test cases and |S| denotes the size of the string.

Time Limit: 1 sec

Solve now

Approaches

01 Approach

The idea here is to make substrings from left and right recursively.
At each step, we try to make a substring from the left side and match it with the right side substring. For every such match, we’ll recursively find the length of the longest chunked palindrome in the remaining strings. Basically, we are not sure about a particular match that will result in the longest length or not. That’s why we have to call the recursive function in every match with the remaining string.
To avoid the function to again compute the result for the same function call, we can save the previously called function’s output.

Steps:

Create a HashMap named savePrev, which is used to store the result of previous function calls.
Call the function solve(S, l, r, savePrev), where ‘S’ is the input string, ‘l’ is initially 0, ‘r’ is initially S.length() - 1, and ‘savePrev’ is the HashMap just created.
Return the return value of the above function.

int solve(string S, int l, int r, HashMap savePrev):

If l > r, then simply return 0.
If the substring S[l:r] is already present in the HashMap, then return the stored value.
Declare a variable ans to 1.
Run a loop from i = 1 to i <= (r - l + 1) / 2, in each iteration do:
- If substring from the left, i.e. S[l : l+i] is equal to the right substring, i.e., S[r-i+1 : r], then:
  - Call the function again with the change in the parameters value, i.e., solve(S, l+i, r-i, savePrev). Update the ans if it the less, i.e., ans = max(ans, solve(S, l+i, r-i, savePrev) + 2)
Now, store ans into the savePrev first, and then also return the ans.

Solve now

02 Approach

The idea here is to use the Greedy approach with the help of 2 strings.
We maintain two strings named left and right. Whenever they match, we increment our answer by 1. After matching, we have to make both the strings empty to store the following characters. Repeat the same for the remaining string.
Here, we are not calling the function again at every match, as we can say that the 1st first match will always be going to lead to the correct result. That’s the main step of this approach.

Steps:

Create a variable named ans to store the final answer, and initialize it with 0.
Create one more variable, n that will store the length of the string S.
Declare two empty strings named left and right.
Run a loop from i = 0 to i < |S|, in each iteration do:
- Add S[i] in the end of the string left, left = left + S[i].
- Add S[n-i-1] in the front of the string right, right = S[n-i-1] + right.
- If, left is equal to right, then:
  - Increment ans by 1.
  - Make left and right both empty.
Return the ans.

Solve now