1312. Minimum Insertion Steps to Make a String Palindrome

How to solve Minimum Insertion Steps to Make a String Palindrome (LeetCode 1312): the approach in brief

The problem

Given a string s. In one step you can insert any character at any index of the string.

Pattern

Minimum Insertion Steps to Make a String Palindrome is a Dynamic Programming (DP) Patterns problem, in the 2D Array (Longest Common Subsequence - LCS) subpattern. The pattern covers fibonacci, Kadane, knapsack, LCS, LIS, edit distance, grid paths, and word break

Find longest common subsequence between two strings using 2D DP.

Approach outline

1. Consider how dynamic programming can help solve problems involving subsequences and string transformations efficiently.
2. Think about how the problem of making a string a palindrome relates to finding a longest palindromic subsequence within it.
3. Recall that the longest palindromic subsequence can be found using the longest common subsequence (LCS) approach between the string and its reverse.

Complexity

The reference solution runs in O(n^2) time and O(n) space.

Asked at

Minimum Insertion Steps to Make a String Palindrome has been reported in interviews at Amazon, LinkedIn.