Min Chars to Add for Palindrome

JavaView on GFG

Time: O(n)

Space: O(n)

Intuition

Minimum characters to add at front to make string a palindrome. KMP on s + reverse(s).

Algorithm

1Form string: s + "#" + reverse(s). Compute KMP failure function. Answer = n - lps[last].

Common Pitfalls

•LPS (longest palindromic suffix) = LPS of s = LCS(s, reverse(s)) starting from beginning. KMP gives this efficiently.

Min Chars to Add for Palindrome.java

Java

// Approach: Compute KMP failure function on s + '#' + reversed(s). Last failure value = length of palindromic prefix.
// Time: O(n) Space: O(n)
class Solution {
    public static int minChar(String s) {
        String rev = new StringBuilder(s).reverse().toString();
        String concat = s + "$" + rev;
        int[] lps = new int[concat.length()];
        int j = 0;
        for (int i = 1; i < concat.length(); i++) {
            while (j > 0 && concat.charAt(i) != concat.charAt(j)) {
                j = lps[j - 1];
            }
            if (concat.charAt(i) == concat.charAt(j)) {
                j++;
            }
            lps[i] = j;
        }
        return s.length() - lps[concat.length() - 1];
    }
}

Was this solution helpful?