Code Implementation

class Solution:
    def minInsertions(self, s: str) -> int:
        n = len(s)
        dp = [[0]*n for _ in range(n)]
        for length in range(2, n+1):
            for i in range(n-length+1):
                j = i+length-1
                if s[i] == s[j]:
                    dp[i][j] = dp[i+1][j-1]
                else:
                    dp[i][j] = 1 + min(dp[i+1][j], dp[i][j-1])
        return dp[0][n-1]
      

class Solution {
public:
    int minInsertions(string s) {
        int n = s.size();
        vector<vector<int>> dp(n, vector<int>(n, 0));
        for (int length = 2; length <= n; ++length) {
            for (int i = 0; i + length - 1 < n; ++i) {
                int j = i + length - 1;
                if (s[i] == s[j]) {
                    dp[i][j] = dp[i+1][j-1];
                } else {
                    dp[i][j] = 1 + min(dp[i+1][j], dp[i][j-1]);
                }
            }
        }
        return dp[0][n-1];
    }
};
      

class Solution {
    public int minInsertions(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];
        for (int length = 2; length <= n; ++length) {
            for (int i = 0; i + length - 1 < n; ++i) {
                int j = i + length - 1;
                if (s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = dp[i+1][j-1];
                } else {
                    dp[i][j] = 1 + Math.min(dp[i+1][j], dp[i][j-1]);
                }
            }
        }
        return dp[0][n-1];
    }
}
      

var minInsertions = function(s) {
    const n = s.length;
    const dp = Array.from({length: n}, () => Array(n).fill(0));
    for (let length = 2; length <= n; ++length) {
        for (let i = 0; i + length - 1 < n; ++i) {
            let j = i + length - 1;
            if (s[i] === s[j]) {
                dp[i][j] = dp[i+1][j-1];
            } else {
                dp[i][j] = 1 + Math.min(dp[i+1][j], dp[i][j-1]);
            }
        }
    }
    return dp[0][n-1];
};
      

Problem Description

You are given a string s. Your task is to determine the minimum number of insertions needed to make s a palindrome. An insertion means adding a single character at any position in the string. You can insert characters as many times as needed, at any position (including at the beginning or end). The goal is to make the string read the same forwards and backwards (a palindrome) with as few insertions as possible.

• Each insertion adds a single character anywhere in the string.
• All characters are lowercase English letters.
• There is always at least one valid solution.

Thought Process

At first glance, the problem asks how to "fix" a string so that it becomes a palindrome, using the fewest insertions. A brute-force approach might try every possible way to insert characters, but this quickly becomes infeasible for longer strings.

Instead, the key insight is to realize that we want to "align" the string with its reverse, since a palindrome reads the same forwards and backwards. The fewer changes we need, the better. If we can find the largest part of the string that is already a palindrome (or matches its reverse), then we only need to "fix" the rest.

This leads us to think about the problem in terms of subproblems: for any substring, what is the minimum number of insertions needed to make it a palindrome? Dynamic programming is a natural fit for this, since we can build up solutions for larger substrings from smaller ones.

Solution Approach

We use dynamic programming to solve this problem efficiently. The main idea is:

• Let dp[i][j] be the minimum number of insertions needed to make the substring s[i..j] a palindrome.
• If s[i] == s[j], then those two characters "match" and don't require any insertion; so dp[i][j] = dp[i+1][j-1].
• If s[i] != s[j], then we need to insert a character to match one end or the other. So:
  • We can insert s[j] at position i, so dp[i][j] = 1 + dp[i+1][j].
  • Or insert s[i] at position j+1, so dp[i][j] = 1 + dp[i][j-1].
  • We take the minimum of these two options.
• We fill the table for all substrings of increasing length, starting from length 2 up to the full string.
• The answer is dp[0][n-1], where n is the length of s.

This approach ensures we consider all possible ways to insert characters, but only compute each subproblem once, making it efficient.

Example Walkthrough

Let's walk through the solution with the input s = "mbadm":

• We want to make "mbadm" a palindrome.
• Compare first and last characters: 'm' and 'm'. They match, so focus on the substring "bad".
• Now, "bad":
  • 'b' and 'd' do not match. So, we can:
    • Insert 'd' at the start: "dbad" (now focus on "ba")
    • Insert 'b' at the end: "badb" (now focus on "ad")
  • Both options require further insertions. Ultimately, the minimum is 2 insertions: "mbadbm" or "mbabdm".
• So, the answer is 2.

The dynamic programming table efficiently computes the minimum insertions for each substring, avoiding repeated work.

Time and Space Complexity

• Brute-force approach: Would try all possible insertions, leading to exponential time complexity: O(2^n), which is infeasible for large strings.
• Optimized DP approach:
  • There are O(n^2) substrings (since for each start index, you can have up to n end indices).
  • Each subproblem is solved in O(1) time (just a min and possibly a comparison).
  • So, the total time complexity is O(n^2).
  • The space complexity is also O(n^2) for the DP table.

Summary

The problem of finding the minimum insertions to make a string a palindrome can be solved efficiently using dynamic programming. By breaking the problem into subproblems for each possible substring and reusing solutions, we avoid redundant calculations. The key insight is to compare characters at both ends and decide whether to insert or move inward, always choosing the option that requires fewer insertions. This approach is both elegant and efficient, with O(n^2) time and space complexity.