#1312

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Minimum Insertion Steps to Make a String Palindrome

The problem asks to find the minimum number of insertions to convert a string into a palindrome using dynamic programming.

string dynamic programming

Problem Statement

You are given a string s, and your task is to determine the minimum number of insertions needed to make the string a palindrome. A palindrome reads the same backward as it does forward.

In one step, you can insert any character at any index in the string. The objective is to find how many such insertions are necessary to turn the string into a palindrome.

Examples

Example 1

Input: s = "zzazz"

Output: 0

The string "zzazz" is already palindrome we do not need any insertions.

Example 2

Input: s = "mbadm"

Output: 2

String can be "mbdadbm" or "mdbabdm".

Example 3

Input: s = "leetcode"

Output: 5

Inserting 5 characters the string becomes "leetcodocteel".

Constraints

1 <= s.length <= 500
s consists of lowercase English letters.

Solution Approach

Dynamic Programming Approach

Use dynamic programming to calculate the longest palindromic subsequence (LPS) of the string. The minimum number of insertions needed is the difference between the length of the string and the LPS.

State Transition

Start by building a 2D DP table where each entry dp[i][j] represents the length of the LPS within the substring s[i..j]. Use the transition rules to fill the table, and the final solution is dp[0][n-1], where n is the length of the string.

Optimized Space Complexity

Instead of using an O(n^2) space table, optimize the space complexity to O(n) by maintaining only two 1D arrays to store the current and previous row of the DP table.

Complexity Analysis

Metric	Value
Time	O(n^2)
Space	O(n)

The time complexity of the solution is O(n^2) because we are iterating over all pairs of indices to fill the DP table. The space complexity is O(n) with optimized space usage for the DP table.

What Interviewers Usually Probe

Understanding dynamic programming concepts is key.
Ability to optimize space complexity is important.
Problem-solving skills for state transition dynamic programming are crucial.

Common Pitfalls or Variants

Common pitfalls

Forgetting to account for single character substrings as palindromes.
Improperly updating the DP table, leading to incorrect results.
Failing to optimize space complexity, leading to unnecessary memory usage.

Follow-up variants

Limit the number of insertions to a fixed number.
Modify the problem to find the longest palindromic subsequence instead of minimum insertions.
Extend the problem to work with multi-character insertions or deletions.

FAQ

What is the primary approach for solving the Minimum Insertion Steps to Make a String Palindrome problem?

The primary approach is using state transition dynamic programming to calculate the longest palindromic subsequence and then determining the number of insertions needed.

Why is dynamic programming suitable for this problem?

Dynamic programming is suitable because we can break down the problem into smaller subproblems (substrings) and solve them efficiently using overlapping subproblems and optimal substructure properties.

What are the time and space complexities for solving this problem?

The time complexity is O(n^2) due to the nested loops for filling the DP table, and the space complexity is O(n) with optimized space usage for the DP table.

How can we optimize the space complexity for this problem?

You can optimize space complexity by using only two 1D arrays instead of a 2D table to store the current and previous rows of the DP table.

What are some common pitfalls when solving the Minimum Insertion Steps to Make a String Palindrome?

Common pitfalls include incorrectly updating the DP table, forgetting to consider single-character palindromes, and failing to optimize space usage.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def minInsertions(self, s: str) -> int:
        @cache
        def dfs(i: int, j: int) -> int:
            if i >= j:
                return 0
            if s[i] == s[j]:
                return dfs(i + 1, j - 1)
            return 1 + min(dfs(i + 1, j), dfs(i, j - 1))

        return dfs(0, len(s) - 1)

Solution 2

#### Python3

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def minInsertions(self, s: str) -> int:
        @cache
        def dfs(i: int, j: int) -> int:
            if i >= j:
                return 0
            if s[i] == s[j]:
                return dfs(i + 1, j - 1)
            return 1 + min(dfs(i + 1, j), dfs(i, j - 1))

        return dfs(0, len(s) - 1)

Solution 3

#### Python3

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def minInsertions(self, s: str) -> int:
        @cache
        def dfs(i: int, j: int) -> int:
            if i >= j:
                return 0
            if s[i] == s[j]:
                return dfs(i + 1, j - 1)
            return 1 + min(dfs(i + 1, j), dfs(i, j - 1))

        return dfs(0, len(s) - 1)

Continue Practicing

#1320 minimum distance to type a word using two fingers #1278 palindrome partitioning iii #1255 maximum score words formed by letters