Minimum characters to be added at front to make string palindrome in C++

Minimum characters to be added to make string palindrome

Today we will be learning how to find the minimum characters that need to be added to make a string palindrome.

  • Input : str = “ABC”
  • Output : 2

We can make the above string palindrome as “CBABC” by adding ‘B’ and ‘C’ at the front.

Minimum characters to be added to make string palindrome
  • Start checking the string each time to see if it is a palindrome; if it isn’t, delete the last character and try again. When the string is reduced to either a palindrome or an empty string.
  • The number of characters deleted from the beginning to the end will be the answer because those characters could have been inserted at the beginning of the original string in the order that makes the string a palindrome.

Minimum characters to be added to make string palindrome C++ Code

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

bool ispalindrome(string s)
{
   int l = s.length();
   int j;
 
    for(int i = 0, j = l - 1; i <= j; i++, j--)
    {
     if(s[i] != s[j])
      return false;
    }
   return true;
  }

// Driver code
  int main()
  {
   string s = "BABABAA";
   int cnt = 0;
   int flag = 0;

   while(s.length()>0)
  {
    if(ispalindrome(s))
    {
     flag = 1;
     break;
    }
   else
  {
   cnt++;
   // erase the last element of the string
   s.erase(s.begin() + s.length() - 1);
  }
 }

  if(flag)
  cout << cnt;
}
2