Make Palindrome 2 Codechef problem solution CoderCEO

Make Palindrome 2 Codechef Problem Solution

You are given a binary string $S$ of length $N$ . You want to obtain a palindrome from $S$ by applying the following operation at most $⌊ \frac{N}{2} ⌋$

times:

Choose an index $i (1 \leq i \leq | S |)$ , delete the character $S_{i}$ from $S$ and concatenate the remaining parts of the string. Here $| S |$ denotes the current length of string $S$

For example, if $S =$ 11010, then applying the operation on index $i = 2$ makes $S =$ 1010.

Note that after each operation, the length of the string $S$ 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 $S$ under the given constraints.

Here, $⌊ \frac{N}{2} ⌋$ denotes floor division of the integer $N$ by $2$ . For example, $⌊ \frac{5}{2} ⌋ = 2$ , $⌊ \frac{8}{2} ⌋ = 4$ . 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 $T$ , denoting the number of test cases. The $T$ test cases then follow:

The first line of each test case contains an integer $N$ , denoting the length of the binary string $S$ .

The second line of each test case contains the binary string $S$

Output Format

For each test case, print on a separate line any palindromic string that can be obtained from $S$ by applying the given operation at most $⌊ \frac{N}{2} ⌋$ times.

Constraints

$1 \leq T \leq 1000$
$1 \leq N \leq 100$
$S$ contains only the characters 0 and 1.

Sample Input 1

Sample Output 1

Explanation

Test case $1$ : The given string is already a palindrome.

Test case $2$ : Applying the operation on index $i = 3$ makes $S =$ 00 which is a palindrome.

Test case $3$ : Applying the operation on index $i = 2$ makes $S =$ 111 which is a palindrome.

Test case $4$ : Applying the operation on index $i = 1$ makes $S =$ 10011. Then applying the operation on index $i = 5$ makes $S =$ 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;
}

Make Palindrome 2 Codechef problem solution

Published by Govind Deshmukh on July 20, 2022July 20, 2022