Program to find minimum characters to be added at front to make a string palindrome in C++

Hello! In this article, we are going to learn how to find the minimum number of characters to be added at the front of the string to make the string palindrome. We are going to discuss two methods. 1) Naive method and 2) Efficient method.

First of all, we will see what is a palindrome. A palindrome is a word or a number which reads the same forward as well as backward.

For example:
For the string = “BBDFDBBBB”
Output: 2

For the string = “aaaaa”
Output: 0

Naive method to make string palindrome

For a given string check if it is a palindrome. If it is not, then remove the last character and again check if the remaining string is a palindrome. We do this till we get a palindrome and the number of characters which we delete till now will give us our answer. If in between our string becomes empty, then our answer will be the length of the string. Because we will add all of the characters of the string to make string palindrome.

The naive method takes O(n^2) time complexity and constant extra space.

Let us see the code implementation of the naive method.

#include<bits/stdc++.h> 
using namespace std; 
bool ispalindrome(string s) 
{ 
    int l = s.length(); 
    int j=l-1,i=0; 
    while(j>i){
        if(s[i]!=s[j])
            return false;
        j--;
        i++;
    }
    return true; 
} 
int main() 
{ 
    string A = "BBDFDBBBB"; 
    int ans = 0; 
      
    while(A.length()>0) 
    { 
        int l = A.length();
        if(ispalindrome(A)) //Check if string is a palindrome. 
        { 
             break; 
        } 
        else
        { 
            ans++; 
            A.erase(A.begin() + l-1); //Remove last element of the string 
        } 
    } 
    cout << ans; 
}

Output:

2

Efficient Method

In the efficient method, we use LPS array. LPS array gives us the length of the longest proper prefix which is also a suffix for the string. We concatenate the reverse of the string with the string and find the LPS array for the concatenated string. Now we take the last element of the LPS and subtract it from the length of the original string. This gives us our final answer.

For string = BBDFDBBBB
Concatenated String = BBDFDBBBBBBBBDFDBB
LPS array will be {0, 1, 0, 0, 0, 1, 2, 2, 2, 1, 2, 2, 2, 3, 4, 5, 6, 7}
From the above LPS array we come to know that 7 characters in the original string already
satisfy the palindrome property. Hence the answer is 9-7 = 2.
#include<bits/stdc++.h> 
using namespace std;



// Program to find the LPS array of a text
vector<int>calculate_lps(string txt){ 
    vector<int>Lps(txt.length(),0);
    Lps[0] = 0;                   //Lps[0] is always 0
    int len = 0;
    int i=1;
    while (i<txt.length()){
        if(txt[i]==txt[len]){    //Case 1
            len++;
            Lps[i] = len;
            i++;
            continue;
        }
        else{                   //Case 2
            if(len==0){         //Subcase 1
                Lps[i] = 0;
                i++;
                continue;
            }
            else{              //Subcase 2
                len = Lps[len-1];
                continue;
            }
        }
    }
    return Lps;
}

//Program to find minimum characters to be added at front to make a string palindrome
int solve(string A) {
    int n = A.length();
    string B = A;
    reverse(B.begin(),B.end());
    A = A + B;
    vector<int>lps = calculate_lps(A);
    lps[2*n-1] = min(n, lps[2*n-1]);
    return n-lps[2*n-1];
}
int main(){
    string s = "BBDFDBBBB";
    int ans = solve(s);
    cout<< ans;
}

Output:

2

The efficient method takes O(n) time and O(n) space.

This is it for the article. Hope you understood the algorithm. Thank You!!
Check out my other blog posts-
Constructing LPS array using the naive approach

Leave a Reply

Your email address will not be published. Required fields are marked *