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.
The only argument given is string A.
Return the minimum characters that are needed to be inserted to make the string a palindrome string.
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".
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)
Code in C++