Make Palindrome 2 Codechef Problem Solution

You are given a binary string of length . You want to obtain a palindrome from by applying the following operation at most

times:

  • Choose an index , delete the character from and concatenate the remaining parts of the string. Here denotes the current length of string

For example, if 11010, then applying the operation on index makes 1010.

Note that after each operation, the length of the string decreases by one.

Find any palindrome you can obtain after the operations. It can be proved that it is always possible to obtain a palindrome from under the given constraints.

Here, denotes floor division of the integer by . For example, , . A binary string is a string that consists of only the characters 0 and 1.

Input Format

  • The first line of input contains an integer , denoting the number of test cases. The test cases then follow:
  • The first line of each test case contains an integer , denoting the length of the binary string .
  • The second line of each test case contains the binary string

    Output Format

    For each test case, print on a separate line any palindromic string that can be obtained from by applying the given operation at most times.

    Constraints

    • contains only the characters 0 and 1.

    Sample Input 1

    4
    3
    101
    3
    001
    4
    1011
    6
    010011
    

    Sample Output 1

    101
    00
    111
    1001
    

    Explanation

    Test case : The given string is already a palindrome.

    Test case : Applying the operation on index makes 00 which is a palindrome.

    Test case : Applying the operation on index makes 111 which is a palindrome.

    Test case : Applying the operation on index makes 10011. Then applying the operation on index makes 1001 which is a palindrome.

    				
    					#include <bits/stdc++.h>
    using namespace std;
    
    int main() {
     int t;
     cin>>t;
     while(t--){
         int n;
         string str2;
         cin>>n>>str2;
         string str1=str2;
         reverse(str2.begin(),str2.end());
         int n1=str1.length(),n2=str2.length();
            vector<vector<int>> dp(n1+1,vector<int>(n2+1,0));
            for(int i=1;i<=n1;i++){
                for(int j=1;j<=n2;j++){
                    if(str1[i-1]==str2[j-1]){
                        dp[i][j]=1+dp[i-1][j-1];
                    }
                    else{
                        dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
                    }
                }
            }
            int i=n1,j=n2;
            string ans="";
            while(i>0 && j>0){
                if(str1[i-1]==str2[j-1]){
                    ans=str1[i-1]+ans;
                    i--;j--;
                }
                else if(dp[i-1][j]>dp[i][j-1]){
                   
                    i=i-1;
                }
                else{
                
                    j=j-1;
                }
            }
            cout<<ans<<endl;
     }
     return 0;
    }
    				
    			

    0 Comments

    Leave a Reply

    Avatar placeholder

    Your email address will not be published.