Minimum characters to be added at beginning to make string palindrome

Problem Statement:

You are given a string, you need to tell minimum characters to be added at the beginning to make the string palindrome.

Input : str = “ABC”
Output : 2

Because we can make the string “ABC” palindrome by adding “CB” at the beginning of the string.

This problem can be solved in different methods. Some of them are:

1. Brute Force method
2. LPS array method.

In this method we keep adding characters from the last to the front one by one.

During this, we will check if the string is a palindrome or not.

At the worst case, we need to check characters equal to the half of length of string.

This will take O(n^2) time.

This problem can be solved in O(n) time by using LPS method.

In this method we can take the help of LPS array.

First we take the string and reverse the given string and add a special character. ns = s + $ + rs

Then we build LPS for every index of the string.

Then we take the last value in LPS array and then subtract with the length of the sting.

That will be the given result.