Longest Palindromic Subsequence Problem Statement

Ninja receives a PS5 from Santa, locked in a safe with a password. The password is the length of the longest palindromic subsequence in the given string SECRETCODE. Can you determine this password to help Ninja open the safe?

Input:

The first line contains an integer 'T', indicating the number of test cases. Each test case has two lines: the first line is an integer 'N' representing the length of the string 'SECRETCODE', and the second line contains the string 'SECRETCODE'.

Output:

For each test case, output a single integer on a new line, which is the length of the longest palindromic subsequence in 'SECRETCODE'.

Example:

Input: 2 7 CACBDBA 3 AAA Output: 4 3

Constraints:

1

Question

Longest Palindromic Subsequence Problem Statement

Ninja receives a PS5 from Santa, locked in a safe with a password. The password is the length of the longest palindromic subsequence in the given string SECRETCODE. Can you determine this password to help Ninja open the safe?

Input:

The first line contains an integer 'T', indicating the number of test cases. Each test case has two lines: the first line is an integer 'N' representing the length of the string 'SECRETCODE', and the second line contains the string 'SECRETCODE'.

Output:

For each test case, output a single integer on a new line, which is the length of the longest palindromic subsequence in 'SECRETCODE'.

Example:

Input: 
2
7
CACBDBA
3
AAA
Output: 
4
3

Constraints:

1 <= T <= 10
1 <= N <= 10³

Note: 'SECRETCODE' consists only of English uppercase letters.

Accepted Answer

The task is to find the length of the longest palindromic subsequence in a given string.

Iterate through the string and create a 2D array to store the lengths of palindromic subsequences.
Use dynamic programming to fill the array based on the characters of the string.
The final answer will be the value at the last index of the array.
Example: For input 'CACBDBA', the longest palindromic subsequence is 'CBDC', so the output will be 4.

Longest Palindromic Subsequence Problem Statement

Input:

Output:

Example:

Constraints:

Microsoft Corporation Software Developer Intern interview questions & answers

Popular interview questions of Software Developer Intern