Longest Chunked Palindrome Decomposition

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
3 upvotes
Asked in company
Samsung

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
1
abcdefgdefabc
Sample Output 1 :
5
Explanation for sample input 1 :
We can split the string into “(abc)(def)(g)(def)(abc)”.
Sample Input 2 :
1
ninjas
Sample Output 2 :
1
Explanation for sample input 2 :
We can split the string into “(ninjas)”.
Hint

Think Recursively.

Approaches (2)
Recursive Approach with Memoization
  • 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.
Time Complexity

O(N^2), where ‘N’ is the size of the input string.

 

In each function call, we are traversing the string once, but whenever there is a match (to compare the string ‘O(length of the string)’ time required), we call the function again with the remaining substring. Hence the overall time complexity will be O(N^2).

Space Complexity

O(N^2), where ‘N’ is the size of the input string.

 

As we are using an additional memory in terms of HashMap, which will store the output of the previous function’s call. We have to deal with the substrings in each function call, and overall N^2 substrings are possible. Hence, the space complexity will be O(N^2).

Code Solution
(100% EXP penalty)
Longest Chunked Palindrome Decomposition
Full screen
Console