Home » Interview Questions » String Interview Questions » Minimum insertions to form a shortest palindrome

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

 

How useful was this post?

Click on a star to rate it!

Average rating / 5. Vote Count

No votes so far! Be the first to rate this post.

We are sorry that this post was not useful for you!

Let us improve this post!

Tell us how we can improve this post?

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions