Table of Contents
Given a string, write a function that will print the least number of charcaters that should be added on to the left side of the string
Example
INPUT
s = “dcb”
OUTPUT
2
“bc” characters should be added on to the left side to make it a palindrome
Algorithm
1. Traverse from the end of the string, if the string s[0…i] is a palindrome then print (n-i-1) as the least number of characters to be added
Implementation for above example:
s = “dcb”
i = 2, s[0..i] ie, “dcb” it is not a palindorme so reduce i
i = 1, s[0..i] ie, “dc” it is not a palindorme so reduce i
i = 0, s[0..i] ie, “da” it is a palindorme so print (n-i-1) ie, (3-0-1) = 2
C++ Program
#include <bits/stdc++.h>
using namespace std;
//Return True if the given string is a palindrome
//function to check if s is palindroem
bool isPalindrome(string s, int start, int end)
{
while (start < end)
{
if (s[start++] != s[end--])
return false;
}
return true;
}
//Prints the number of minimum characters to be inserted on left to make it a palindrome
void printMinToBeInserted(string s)
{
int n = s.length();
//traverse from end to start
for (int i = n-1; i >= 0; --i)
{
if (isPalindrome(s,0,i))
{
cout<<"Minimum characters to be inserted is "<<(n-i-1)<<endl;
}
}
}
int main()
{
string s = "dcb";
printMinToBeInserted(s);
}