Minimum Insertion Steps to Make a String Palindrome - Solution & Explanation

Problem Overview: Given a string s, compute the minimum number of characters you must insert anywhere in the string so the final string becomes a palindrome. Insertions can be made at any position, but existing characters cannot be removed or reordered.

Approach 1: Dynamic Programming (Longest Palindromic Subsequence) (Time: O(n^2), Space: O(n^2))

The key observation: the minimum insertions required equals n - LPS, where LPS is the length of the Longest Palindromic Subsequence. A subsequence that is already palindromic does not require changes; you only insert characters to mirror the missing parts. Compute LPS by finding the Longest Common Subsequence between the string and its reverse. Use a 2D DP table where dp[i][j] stores the LCS length for prefixes of the original and reversed string. The final answer becomes n - dp[n][n]. This approach is stable, easy to reason about, and widely expected in interviews involving dynamic programming and string problems.

Approach 2: Recursion with Memoization (Time: O(n^2), Space: O(n^2))

Work directly on the palindrome property using two pointers. Define a recursive function on substring indices (i, j). If s[i] == s[j], both characters can stay in the palindrome, so recurse on (i+1, j-1). If they differ, you must insert a matching character on either side, which means taking 1 + min(f(i+1, j), f(i, j-1)). Memoize results in a 2D cache to avoid recomputation of overlapping subproblems. This formulation mirrors how palindromes are built from both ends and is a natural application of dynamic programming over substrings.

Recommended for interviews: The Longest Palindromic Subsequence transformation is usually the expected explanation because it reduces the problem to a well-known DP pattern. Mentioning the recursive two‑pointer formulation shows deeper understanding of palindrome structure, but implementing the LPS DP tends to be cleaner and easier to debug under time pressure.