Decode String

Easy
0/40
1 upvote
Asked in companies
Disney + HotstarMicrosoftIntuit

Problem statement

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.


Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
7
ABCGDBA 
5
DBADE
Sample Output 1 :
4
3
Explanation of sample output 1:
Test Case 1:

'SECRETCODE' is 'ABCGDBA'.
18 palindromic subsequences exist, ‘A’, ‘B’, ‘C’, ‘G’, ‘D’, ‘AA’, ‘BB’, ‘ABA’, 'ACA', 'AGA', 'ADA', 'BCB', BGB', 'BDB', ‘ABBA’,  'ABCBA', 'ABGBA' and 'ABDBA' among which the longest palindromic subsequences are 'ABCBA', 'ABGBA' and 'ABDBA' each of length 5.



Test Case 2:

'SECRETCODE' is 'DBADE'.
'DBD' and 'DAD' are the longest palindromic subsequences each of length 3.
Sample Input 2:
2
8
ADEBCBDP  
5
CCCCC
Sample Output 2:
5
5
Explanation of sample output 2:
Test Case 1:

'SECRETCODE' is 'ADEBCBDP'.
'DBCBD' is the longest palindromic subsequence of length 5.


Test Case 2:

'SECRETCODE' is 'CCCCC'.
‘CCCCC’ is also a subsequence of ‘CCCCC’ which is a palindrome of length 5.
Hint

Try checking for all the substrings but one at a time.

 

Approaches (3)
Brute Force

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 -  

 

  1. 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.
  2. 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).
  3. 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.
  4. Base cases:
    1. If ‘i’ < ’j’ return 0.
    2. If ‘i’ == ’j’, we return 1 as for a string with length ‘1’, the longest palindromic subsequence will be of length 1.
Time Complexity

O(2 ^ N), where ‘N’ is the length of the given string in ‘SECRETCODE’.

 

In the worst case when SECRETCODE[i] != SECRETCODE[j], each call will further invokes 2 more recursive calls. Hence, the overall time complexity is O(2 ^ N).

Space Complexity

O(N), where ‘N’ is the length of given string in ‘SECRETCODE’.

 

We are not using any external data structure. Only recursion stack space of O(N) size is used by the algorithm.

 

Code Solution
(100% EXP penalty)
Decode String
Full screen
Console