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

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

 


Next > < Prev
Scroll to Top