Minimum appends to make string Palindrome | Strings | C++

 

Minimum Appends to Make string Palindrome

A Palindrome is a sequence of characters that has the property of reading the same in either direction.

You are given a string str. Find minimum characters required to append at the end of string str to make it a palindrome. In case str is already a palindrome print "NULL".

NOTE:

• The string str will contain only lowercase English alphabets.

Input Format:

The input consists of two lines:

• The first line contains an integer, i.e. the length of str.
• The second line contains a string, i.e. str.

Output Format:

The output consists of minimum characters needed to make str palindrome or "NULL"  in case str is already a palindrome.

Example:

Input:

5

abede

Output:

ba

Explanation:

 if we append 'ba' at the end of the string str 'abede', it becomes 'abedeba' (i.e. A palindrome string).

Algorithm:

We first calculate the number of unmatched characters from the ith position i.e. characters that are not the same from the ith position and last position.

After calculating the number of characters that are missing (say k) to make the string palindrome we add letter to our res string from the k-1 position till 0th index by decreasing the counter because those are the missing characters from str to make it a palindrome.

Solution in C++:

#include <bits/stdc++.h>

using namespace std;

bool isPalindrome(string& s,int i)

{

    int f = i;

    int l = s.length() - 1;

    while(f<l){

        if(s[f]!=s[l]) return false;

        f++;

        l--;

    }

    return true;

}

 

int noOfAppends(string& s,int i)

{

    if (isPalindrome(s,i))

        return 0;

    i++;

    return 1 + noOfAppends(s, i);

}

string qs(string& s){

    int x = noOfAppends(s,0);

    string res;

    for(int i=x-1;i>=0;i--) res += s[i];

    return res;

}

int main() {

    int n;

    cin>>n;

    string s;

    cin>>s;

    cout<<qs(s)<<"\n";

    return 0;

}

 Time complexity: O(N^2)

All test cases passed.

Thank you and keep learning.

For any queries comment below.