Leetcode 1312. Minimum Insertion Steps to Make a String Palindrome

Problem Explanation:

The problem is asking to return the minimum number of steps (insertions) required to make the given string a palindrome. A palindrome is a word that reads the same backwards as forwards, like "radar" or "madam".

The solution to this problem is based on finding the length of the longest palindrome subsequence present in the original string and then deducting that length from the length of the original string. The result is the minimum number of steps required to make the string a palindrome. This is a dynamic programming approach as it breaks down the problem into simpler sub-problems and then combines them to get the final result.

The key component of this solution is finding the longest palindromic subsequence in a given string. This is achieved by creating a 2D array ( dp[i][j] ) where i and j represents the start and end indices of a subsequence in the original string. If the characters at i and j are same, then the value of dp[i][j] is calculated as 2 plus the value of dp[i+1][j-1] (representing a subsequence that is smaller by 2 characters), otherwise it is the maximum of dp[i+1][j] and dp[i][j-1] (representing subsequences that are smaller by 1 character).

Let's take the string "mbadm" as an example. The length of the longest palindromic subsequence is 3 (i.e., "bmb"). Therefore, we require at least (5-3)=2 insertions to make "mbadm" palindrome. We can insert 'b' and 'm' at 0th and 5th position to get "bmbdam".

Solutions:

Python Solution:

1
2python
3class Solution:
4    def minInsertions(self, s: str) -> int:
5        n = len(s)
6        # Initialize dp array
7        dp = [[0]*n for _ in range(n)]
8        for i in range(n-1,-1,-1):
9            dp[i][i] = 1
10            for j in range(i+1,n):
11                if s[i] == s[j]:
12                    dp[i][j] = 2 + dp[i+1][j-1] 
13                else:
14                    dp[i][j] = max(dp[i+1][j],dp[i][j-1])
15        # Return minimum number of insertions needed
16        return n - dp[0][n-1]

Java Solution:

1
2java
3class Solution {
4    public int minInsertions(String s) {
5        int n = s.length();
6        // Initialize dp array
7        int[][] dp = new int[n][n];
8        for (int i = n - 1; i >= 0; i--) {
9            dp[i][i] = 1;
10            for (int j = i + 1; j < n; j++) {
11                if (s.charAt(i) == s.charAt(j)) {
12                    dp[i][j] = 2 + dp[i + 1][j - 1];
13                } else {
14                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
15                }
16            }
17        }
18        // Return minimum number of insertions needed
19        return n - dp[0][n - 1];
20    }
21}

C# Solution:

1
2csharp
3public class Solution {
4    public int MinInsertions(string s) {
5        int n = s.Length;
6        // Initialize dp array
7        int[,] dp = new int[n, n];
8        for (int i = n - 1; i >= 0; i--) {
9            dp[i, i] = 1;
10            for (int j = i + 1; j < n; j++) {
11                if (s[i] == s[j]) {
12                    dp[i, j] = 2 + dp[i + 1, j - 1];
13                } else {
14                    dp[i, j] = Math.Max(dp[i + 1, j], dp[i, j - 1]);
15                }
16            }
17        }
18        // Return minimum number of insertions needed
19        return n - dp[0, n - 1];
20    }
21}

C++ Solution:

1
2c++
3class Solution {
4public:
5    int minInsertions(string s) {
6        int n = s.size();
7        // Initialize dp array
8        vector<vector<int>> dp(n, vector<int>(n));
9        for (int i = n - 1; i >= 0; i--) {
10            dp[i][i] = 1;
11            for (int j = i + 1; j < n; j++) {
12                if (s[i] == s[j]) {
13                    dp[i][j] = 2 + dp[i + 1][j - 1];
14                } else {
15                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
16                }
17            }
18        }
19        // Return minimum number of insertions needed
20        return n - dp[0][n - 1];
21    }
22};

Javascript Solution:

1
2javascript
3var minInsertions = function(s) {
4    const n = s.length;
5    // Initialize dp array
6    let dp = Array.from({length: n}, () => Array(n).fill(0));
7    for(let i=n-1; i>=0; i--){
8        dp[i][i] = 1;
9        for(let j=i+1; j<n; j++){
10            if(s.charAt(i) == s.charAt(j)){
11                dp[i][j] = 2+dp[i+1][j-1];
12            }
13            else{
14                dp[i][j] = Math.max(dp[i+1][j],dp[i][j-1]);
15            }
16        }
17    }
18    // Return minimum number of insertions needed
19    return n - dp[0][n-1];
20};

Kotlin Solution:

1
2kotlin
3class Solution {
4    fun minInsertions(s: String): Int {
5        val n = s.length
6        // Initialize dp array
7        val dp = Array(n) { IntArray(n) }
8        for (i in n - 1 downTo 0) {
9            dp[i][i] = 1
10            for (j in i + 1 until n) {
11                dp[i][j] = if (s[i] == s[j]) 2 + dp[i + 1][j - 1] else maxOf(dp[i + 1][j], dp[i][j - 1])
12            }
13        }
14        // Return minimum number of insertions needed
15        return n - dp[0][n - 1]
16    }
17}

Every solution here uses the same dynamic programming approach to solve the problem in similar ways across different languages.

All of these solutions use a 2D array to find the length of the longest palindrome subsequence in the string. This palindromic subsequence is then subtracted from the length of the original string to find the minimum number of insertions required to convert the original string to a palindrome.

Remember that the key to solving dynamic programming problems is to break down the problem into smaller sub-problems, solve each of them independently and then combine the solutions to get the result for the original problem. This problem follows the same approach by breaking down the original string into smaller substrings and then finding the longest palindromic subsequence among them.

This problem analysis and solution can be further applied to similar problems in the area of dynamic programming and string manipulations such as finding the longest common subsequence, longest common substring, least common supersequence among strings, and more.