Minimum insertions to form a shortest palindrome  

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

Please click Like if you loved this article?

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);
}

Try It

 

See also
Word Pattern
Please click Like if you loved this article?

Ads Blocker Image Powered by Code Help Pro
Ads Blocker Detected!!!

This website does not work properly with AdBlock. We have detected that you are using extensions to block ads. Please disable Adblocker to view the content.

Refresh