Minimum Characters required to make a String Palindromic InterviewBit Solution

Problem: Minimum Characters required to make a String Palindromic

Problem Statement:

Given a string A. The only operation allowed is to insert characters at the beginning of the string.

Find how many minimum characters are needed to be inserted to make the string a palindrome string.

Input Format

The only argument given is string A.

Output Format

Return the minimum characters that are needed to be inserted to make the string a palindrome string.

For Example

Input 1:
    A = "ABC"
Output 1:
    2
    Explanation 1:
        Insert 'B' at beginning, string becomes: "BABC".
        Insert 'C' at beginning, string becomes: "CBABC".

Input 2:
    A = "AACECAAAA"
Output 2:
    2
    Explanation 2:
        Insert 'A' at beginning, string becomes: "AAACECAAAA".
        Insert 'A' at beginning, string becomes: "AAAACECAAAA".

Approach:

Each index of the LPS array contains the longest prefix which is also a suffix. Now take the string and reverse of a string and combine them with a sentinel character in between them and compute the LPS array of this combined string. Now take the last value of the LPS array and subtract it with the length of the original string, This will give us the minimum number of insertions required at the beginning of the string.

Time & Space Complexity:

Time Complexity: O(N)

Solution:

Code in C++