Last Updated: 13 Jan, 2021
Decode String
Easy
Asked in companies
Ninja requests a PS5 from Santa on Christmas. Santa decides to give Ninja a brand new PS5, but he locks it in a safe and gives Ninja a string SECRETCODE. The password to open the safe is the length of the longest palindromic subsequence present in SECRETCODE.
A palindromic subsequence is a subsequence (generated by deleting some character of a given string without changing its order) which is a palindrome. For example: ‘ABBA’ is the longest palindromic subsequence for ‘CACBDBA’.
As Ninja is busy sending Christmas presents to his friends, he asks you for help. Can you help Ninja open the safe and retrieve his PS5?
Note:
‘SECRETCODE’ consists of only English uppercases.
Input Format:
The first line of input contains an integer 'T' representing the number of test cases or queries to be processed. Then the test case follows.
The first line of each test case contains a single integer ‘N’ where ‘N’ denotes the length of 'SECRETCODE'.
The second line of each test case contains the string 'SECRETCODE'.
Output Format :
For each test case, print a single integer denoting the length of longest palindromic subsequence present in the given string 'SECRETCODE'.
Print the output of each test case in a separate line.
Note :
You do not need to print anything; it has already been taken care of. Just implement the function.
Constraints:
1 <= T <= 10
1 <= N <= 10^3
Where ‘T’ is the total number of test cases and ‘N’ denotes the length of 'SECRETCODE'
Time limit: 1 second
Approaches
We use recursion to solve this problem. If the two ends of a string are the same, then they must be included in the longest palindrome subsequence. Otherwise, both ends cannot be included in the longest palindrome subsequence.
Here is the complete algorithm -
- We call our helper function decodeStringHelper which will take 3 parameters ‘i’, ’j’ and ‘’ where ‘i’, ‘j’ and ‘SECRETCODE’ are the starting index, ending index and string ‘SECRETCODE’, respectively.
- If SECRETCODE[i] == SECRETCODE[j], that means both the values from left and right are equal so they can be included in our answer. So, we compute the same for the rest of the string and add 2 to the answer i.e. return 2 + decodeStringHelper (i + 1, j - 1).
- If SECRETCODE[ i ] != SECRETCODE[ j ] that means the characters are different. So, we recur for (i + 1, j) and (i, j - 1) and return the maximum of the two as our answer.
- Base cases:
- If ‘i’ < ’j’ return 0.
- If ‘i’ == ’j’, we return 1 as for a string with length ‘1’, the longest palindromic subsequence will be of length 1.
We are solving this problem by solving its subproblems and then combining their solutions. If we analyze carefully, we will see that we are solving the same subproblems multiple times. Thus, this problem exhibits overlapping subproblems. So, in this approach, we will eliminate the need for solving the same subproblems again and again by using memoization.
Algorithm:
The algorithm is similar to the previous approach with some additions.
We create a 2D table ‘lookUp’ of size N * N (where ‘N’ denotes the length of 'SECRETCODE') to store the solutions to the subproblems. lookUp[ i ][ j ] denotes the longest palindromic subsequence for substring from ‘i’ to ‘j’ ’ We initialize the table by -1.
- If we have already computed the result for ‘i’ to ‘j’ i.e. lookUp[ i ][ j ] != 0, then we simply return this pre-computed result lookUp[ i ][ j ].
- If ‘SECRETCODE[ i ] == SECRETCODE[ j ]’, we compute the result for (i + 1,j - 1) and update lookup table as lookUp[ i ][ j ] = 2 + decodeStringHelper(i + 1, j - 1).
- If ‘SECRETCODE[ i ] != SECRETCODE[ j ]’, we compute the result as the maximum of (i + 1, j) and (i, j - 1) and update the lookup table i.e. lookUp[ i ][ j ] = max(decodeStringHelper(i + 1, j), decodeStringHelper(i, j - 1)).
- We return the updated value of lookUp[i][j] as the answer.
We implement the above idea in the bottom-up approach. We try all the possible substring lengths and compute the answer for each of them and then update the answer in ‘dp’ matrix.
The idea is to create a 2-D array ‘dp’ of size (N + 1)*N initialised to 0. dp[i][j] denotes the maximum length palindromic subsequence of the substring of the ‘SECRETCODE’ from ‘i’ to ‘j’.
We compute the value for each substring starting from ‘1’ to ‘N’ where ‘N’ is the length of ‘SECRETCODE’.
- Initially, we set dp[1][j] = 1 as a string of length 1 is also a palindromic subsequence.
- We run two nested loops from i = 2 to N and j = 0 to N - i, where i and j are used to fix starting and ending indices of substrings of the given string.
- If SECRETCODE[ i ] == SECRETCODE[ i + j - 1], we set dp[ i ][ j ] = 2 + max(dp[i + 1, j], dp[i, j - 1]).
- Else, we set dp[ i ][ j ] = max(dp[i + 1][ j ], dp[ i ][j - 1]).
- Finally, we return dp[n][0] as our answer.