Minimum Characters required to make a String Palindromic

Given an string A. The only operation allowed is to insert characters in 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".

Method 1:

Recursion. We keep checking if current string is palindrome, if not, we increase count by one and remove last element from the string, and then keep checking.

Solution:

Time: O(n^2)
Space: O(1)

public class Solution {
    public int solve(String A) {
        int count = 0;
        if (isP(A)) return count;
        return 1 + solve(A.substring(0, A.length() - 1));
    }
    
    private boolean isP(String A) {
        int left = 0;
        int right = A.length() - 1;
        while (left <= right) {
            if (A.charAt(left) == A.charAt(right)) {
                left ++;
                right --;
            } else {
                return false;
            }
        }
        return true;
    }
}

Method 2:

Each index of 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 sentinal 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 in the beginning of the string

Solution:

Time: O(n)
Space: O(n)

public class Solution {
    public int solve(String A) {
        String reversed = new StringBuilder(A).reverse().toString();
        String str = A + "$" + reversed;
        int[] table = buildFallBackTable(str);
        return A.length() - (table[2 * A.length()] + 1);
    }
    
    private int[] buildFallBackTable(String str) {
        int n = str.length();
        int[] table = new int[n];
        table[0] = -1;
        int fallBackIndex = -1;
        for (int currentIndex = 1; currentIndex < n; currentIndex ++) {
            while(fallBackIndex >= 0 && str.charAt(fallBackIndex + 1) != str.charAt(currentIndex)) {
                fallBackIndex = table[fallBackIndex];
            }
            if (str.charAt(fallBackIndex + 1) == str.charAt(currentIndex)) {
                fallBackIndex ++;
            }
            table[currentIndex] = fallBackIndex;
        }
        return table;
    }
}