Algorithm


 problem Link :  https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=1394 

By definition palindrome is a string which is not changed when reversed. “MADAM” is a nice example of palindrome. It is an easy job to test whether a given string is a palindrome or not. But it may not be so easy to generate a palindrome. Here we will make a palindrome generator which will take an input string and return a palindrome. You can easily verify that for a string of length n, no more than (n−1) characters are required to make it a palindrome. Consider ‘abcd’ and its palindrome ‘abcdcba’ or ‘abc’ and its palindrome ‘abcba’. But life is not so easy for programmers!! We always want optimal cost. And you have to find the minimum number of characters required to make a given string to a palindrome if you are allowed to insert characters at any position of the string. Input Each input line consists only of lower case letters. The size of input string will be at most 1000. Input is terminated by EOF. Output For each input print the minimum number of characters and such a palindrome separated by one space in a line. There may be many such palindromes. Any one will be accepted. Sample Input abcd aaaa abc aab abababaabababa pqrsabcdpqrs

Sample Output 3 abcdcba 0 aaaa 2 abcba 1 baab 0 abababaabababa 9 pqrsabcdpqrqpdcbasrqp

Code Examples

#1 Code Example with C Programming

Code - C Programming

#include <bits/stdc++.h>
using namespace std;

int main()
{
    string in;
    while(getline(cin,in)){
        vector < vector<int>> dp(in.length(),vector<int>(in.length(),1e6));
        vector < vector<int>> decision(in.length(),vector<int>(in.length()));
        for(int len=0;len<in.length();len++){
            for(int left=0;left+len<in.length();left++){
                int right = left+len;
                if(in[left] == in[right]){
                    dp[left][right] = left+1>=right-1 ? 0 : dp[left+1][right-1];
                } else {
                    int leftCost = dp[left][right-1]; // insert on left
                    int rightCost = dp[left+1][right]; // insert on right
                    if(leftCost > rightCost) {
                        dp[left][right] = rightCost+1;
                        decision[left][right] = 1;
                    } else {
                        dp[left][right] = leftCost+1;
                        decision[left][right] = 2;
                    }
                }
            }
        }
        int left=0,right=in.length()-1;
        string leftStr="",rightStr="";
        while(left<=right){
            if(in[left] == in[right]){
                if(left==right) leftStr += in[left];
                else {
                    leftStr += in[left];
                    rightStr += in[left];
                }
                left++; right--;
            } else if(decision[left][right] == 1){
                // insert left character on right
                rightStr += in[left];
                leftStr += in[left];
                left++;
            } else if(decision[left][right] == 2){
                // insert right character on left
                leftStr += in[right];
                rightStr += in[right];
                right--;
            }
        }
        reverse(rightStr.begin(),rightStr.end());
        cout << dp[0][in.length(>-1] << " " << leftStr << rightStr << endl;
    }
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
abcd
aaaa
abc
aab
abababaabababa
pqrsabcdpqrs

Output

x
+
cmd
3 abcdcba
0 aaaa
2 abcba
1 baab
0 abababaabababa
9 pqrsabcdpqrqpdcbasrqp
Advertisements

Demonstration


UVA Online Judge solution - 10453-Make Palindrome - UVA Online Judge solution in C,C++,java

Previous
UVA Online Judge solution - 10452-Marcus - UVA Online Judge solution in C,C++,java
Next
UVA Online Judge solution - 10460-Find the Permuted String - UVA Online Judge solution in C,C++,java