[Solved] Maximizing LCS STARTERS 71 CodeChef

Alice and Bob are playing a game using a string SS of length NN. They both have their individual strings which are initially empty.

Both players take alternate turns. Alice starts first.
In Alice’s turn, she will:

• Choose a prefix of SS;
• Remove the chosen prefix from SS;
• Append the prefix to the end of her string.

In Bob’s turn, he will:

• Choose a suffix of SS;
• Remove the chosen suffix from SS;
• Reverse the suffix and append it to the end of his string.

Chef has decided to reward them if the length of the Longest Common Subsequence (LCS) of Alice’s and Bob’s strings is maximized. Help Chef calculate the length of maximum LCS that can be achieved by Alice and Bob.

Note:

• A prefix is obtained by deleting some (possibly zero) elements from the end of the string.
• A suffix is obtained by deleting some (possibly zero) elements from the beginning of the string.
• Please use fast I/O for input and pypy for python submissions.

Input Format

• The first line of input will contain a single integer TT, denoting the number of test cases.
• Each test case consists of two lines, the first line contains a single integer NN denoting the length of the original string.
• The second line contains the original string SS.

Output Format

For each test case, output the length of the maximum LCS achievable by Alice and Bob.

Constraints

Sample 1:

Input

3
4
abab
6
abccda
4
aaaa

Output

1
2
2

Explanation:

Test case 11: In Alice’s turn, she can pick the prefix S[1, 2] =S[1,2]= ab, and append it to her string. Thus, the remaining string is ab. In Bob’s turn, he can pick the suffix S[1, 2] =S[1,2]= ab, reverse it, and append to his string.
Thus, Alice’s string is ab, and, Bob’s string is ba. The length of the longest common subsequence in these two strings is 11.

Test case 22: In Alice’s turn, she can pick the prefix S[1, 3] =S[1,3]= abc, and append it to her string. Thus, the remaining string is cda. In Bob’s turn, he can pick the suffix S[1, 3] =S[1,3]= cda, reverse it, and append to his string.
Thus, Alice’s string is abc, and, Bob’s string is adc. The length of the longest common subsequence in these two strings is 22.

Test case 33: In Alice’s turn, she can pick the prefix S[1, 2] =S[1,2]= aa, and append it to her string. Thus, the remaining string is aa. In Bob’s turn, he can pick the suffix S[1, 2] =S[1,2]= aa, reverse it, and append to his string.
Thus, Alice’s string is aa, and, Bob’s string is aa. The length of the longest common subsequence in these two strings is 22.

Problem: https://www.codechef.com/START71D/problems/MAXLCS

Solution

/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
	public static void main (String[] args) throws java.lang.Exception
	{
	  Scanner sc=new Scanner(System.in);
        int t=sc.nextInt();
        while(t-->0){
            int n=sc.nextInt();
            String s=sc.next();
            String s1=new StringBuilder(s).reverse().toString();
            int[][] arr=new int[n+1][n+1];
            for(int i=1;i<=n;i++){
                // sauravhathi
                for(int j=1;j<=n;j++){
                    if(s.charAt(i-1)==s1.charAt(j-1)){
                        arr[i][j]=arr[i-1][j-1]+1;
                    }
                    else{
                        arr[i][j]=Math.max(arr[i-1][j],arr[i][j-1]);
                    }
                }
            }
            System.out.println(arr[n][n]/2);
        }
	}
}

Happy Learning – If you require any further information, feel free to contact me.