Minimum characters to be added at front to make string palindrome

Problem Statement

Given a string, find the minimum number of characters to be added at the front of the string to make it a palindrome.

Example:

• Input: "AACECAAAA"
• Output: 2
• Explanation: Add "AA" at front to get "AAAACECAAAA" which is a palindrome

Example 2:

• Input: "ABC"
• Output: 2
• Explanation: Add "CB" at front to get "CBABC"

Approach 1: Brute Force (Check Each Prefix)

Intuition

Find the longest palindromic prefix. Characters after this prefix need to be added in reverse at the front.

Algorithm

1. For each length l from n down to 1
2. Check if prefix of length l is a palindrome
3. When found, answer is n - l (characters outside the palindromic prefix)

public class Solution {
    private boolean isPalindrome(String s, int len) {
        int left = 0, right = len - 1;
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
    
    public int minCharsToAddForPalindrome(String s) {
        int n = s.length();
        
        for (int len = n; len >= 1; len--) {
            if (isPalindrome(s, len)) {
                return n - len;
            }
        }
        
        return n - 1;
    }
}

Complexity Analysis

• Time Complexity: O(n²) - Checking up to n prefixes, each takes O(n)
• Space Complexity: O(1)

Approach 2: Using LPS Array (KMP) - Optimal

Intuition

Create a new string: s + "$" + reverse(s). The LPS (Longest Proper Prefix which is also Suffix) array of this string tells us the longest palindromic prefix of the original string.

Why This Works

• If original string has a palindromic prefix of length k
• Then the first k characters of s match the last k characters of reverse(s)
• The LPS value at the end tells us this length

Algorithm

1. Create concatenated string: s + "$" + reverse(s)
2. Compute LPS array using KMP preprocessing
3. LPS value at the last position gives the longest palindromic prefix length
4. Answer = n - LPS[last]

public class Solution {
    private int[] computeLPS(String pattern) {
        int m = pattern.length();
        int[] lps = new int[m];
        
        int len = 0;
        int i = 1;
        
        while (i < m) {
            if (pattern.charAt(i) == pattern.charAt(len)) {
                len++;
                lps[i] = len;
                i++;
            } else {
                if (len != 0) {
                    len = lps[len - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }
        
        return lps;
    }
    
    public int minCharsToAddForPalindrome(String s) {
        int n = s.length();
        if (n == 0) return 0;
        
        // Create concatenated string
        String rev = new StringBuilder(s).reverse().toString();
        String concat = s + "$" + rev;
        
        // Compute LPS array
        int[] lps = computeLPS(concat);
        
        // Longest palindromic prefix length
        int longestPalindromicPrefix = lps[lps.length - 1];
        
        return n - longestPalindromicPrefix;
    }
}

Dry Run Example

Complexity Analysis

• Time Complexity: O(n) - LPS computation is linear
• Space Complexity: O(n) - For concatenated string and LPS array

Approach 3: Two Pointer with Recursion

Intuition

Compare characters from both ends. When they match, both are part of the palindrome. When they don't, we must add the rightmost character at the front.

Note

This approach gives correct answer but has O(n) time in best case and O(n) in worst case when the string is already a palindrome or nearly so. However, it's not optimal for all cases as it may miss some optimizations.

Key Takeaways

1. LPS (KMP) approach is the optimal O(n) solution
2. Key insight: Find longest palindromic prefix starting from index 0
3. Characters not in the palindromic prefix need to be added in reverse at front
4. The separator "$" prevents false matches between s and reverse(s)
5. This technique (concatenation with separator + LPS) is useful for many pattern matching problems
6. Related: Shortest Palindrome (LeetCode 214)