LeetCode 1312: Minimum Insertion Steps to Make a String Palindrome Solution

Master LeetCode problem 1312 (Minimum Insertion Steps to Make a String Palindrome), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1312. Minimum Insertion Steps to Make a String Palindrome

Hard

String Dynamic Programming

Problem Explanation

Explanation

To solve this problem, we can use dynamic programming. We can define a 2D array dp where dp[i][j] represents the minimum number of insertions needed to make the substring s[i...j] a palindrome. We can fill in this 2D array diagonally from bottom right to top left.

If the characters at indices i and j are equal, then we do not need any insertions (dp[i][j] = dp[i+1][j-1]). Otherwise, we need to consider two cases:

Inserting a character at index i (dp[i][j] = 1 + dp[i+1][j])
Inserting a character at index j (dp[i][j] = 1 + dp[i][j-1])

The final answer will be in dp[0][n-1], where n is the length of the input string s.

Time complexity: O(n^2), where n is the length of the input string Space complexity: O(n^2)

Solution Code

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

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1312 (Minimum Insertion Steps to Make a String Palindrome)?

This page provides optimized solutions for LeetCode problem 1312 (Minimum Insertion Steps to Make a String Palindrome) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1312 (Minimum Insertion Steps to Make a String Palindrome)?

The time complexity for LeetCode 1312 (Minimum Insertion Steps to Make a String Palindrome) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1312 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1312 in Java, C++, or Python.

Back to LeetCode Solutions