Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1312.html

1312. Minimum Insertion Steps to Make a String Palindrome (Hard)

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

Return the minimum number of steps to make s palindrome.

Palindrome String is one that reads the same backward as well as forward.

 

Example 1:

Input: s = "zzazz"
Output: 0
Explanation: The string "zzazz" is already palindrome we don't need any insertions.

Example 2:

Input: s = "mbadm"
Output: 2
Explanation: String can be "mbdadbm" or "mdbabdm".

Example 3:

Input: s = "leetcode"
Output: 5
Explanation: Inserting 5 characters the string becomes "leetcodocteel".

Example 4:

Input: s = "g"
Output: 0

Example 5:

Input: s = "no"
Output: 1

 

Constraints:

  • 1 <= s.length <= 500
  • All characters of s are lower case English letters.

Related Topics:
Dynamic Programming

Solution 1. DP

This problem is similar to “given two strings s and t, count how many insertions are needed to make them the same”.

In this problem, t is the reversed s.

Let dp[i][j] be the minimum insertions needed to make s[0..(i-1)] and t[0..(j-1)] the same.

dp[i][j] = dp[i-1][j-1]                     If s[i-1] == t[j-1]
         = 1 + min(dp[i-1][j], dp[i][j-1])  If s[i-1] != t[j-1]
dp[0][i] = dp[i][0] = i

The answer of this problem is dp[N][N] / 2.

// OJ: https://leetcode.com/problems/minimum-insertion-steps-to-make-a-string-palindrome/
// Time: O(N^2)
// Space: O(N^2)
class Solution {
public:
    int minInsertions(string s) {
        int N = s.size();
        string t(s.rbegin(), s.rend());
        vector<vector<int>> dp(N + 1, vector<int>(N + 1));
        for (int i = 0; i <= N; ++i) {
            for (int j = 0; j <= N; ++j) {
                if (i == 0 || j == 0) dp[i][j] = i + j;
                else if (s[i - 1] == t[j - 1]) dp[i][j] = dp[i - 1][j - 1];
                else dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return dp[N][N] / 2;
    }
};

Solution 2. DP + Space Optimization

Since dp[i][j] is only dependent on dp[i-1][j-1], dp[i-1][j] and dp[i][j-1], we can reduce the space of dp array from N * N to 1 * N with a temporary variable storing dp[i-1][j-1].

// OJ: https://leetcode.com/problems/minimum-insertion-steps-to-make-a-string-palindrome/
// Time: O(N^2)
// Space: O(N)
class Solution {
public:
    int minInsertions(string s) {
        int N = s.size();
        vector<int> dp(N + 1);
        for (int i = 0; i <= N; ++i) {
            int prev;
            for (int j = 0; j <= N; ++j) {
                int cur = dp[j];
                if (i == 0 || j == 0) dp[j] = i + j;
                else if (s[i - 1] == s[N - j]) dp[j] = prev;
                else dp[j] = 1 + min(dp[j], dp[j - 1]);
                prev = cur;
            }
        }
        return dp[N] / 2;
    }
};;

Solution 3. Longest Palindrome Subsequence

If we know the length of the longest palindrome subsequence of s is M, then the answer to this problem would be s.size() - M.

So we can reuse the solution to 516. Longest Palindromic Subsequence (Medium).

// OJ: https://leetcode.com/problems/minimum-insertion-steps-to-make-a-string-palindrome/
// Time: O(N^2)
// Space: O(N)
class Solution {
    int longestPalindromeSubseq(string &s) {
        int N = s.size();
        vector<int> dp(N + 1);
        for (int i = 1; i <= N; ++i) {
            int prev = 0;
            for (int j = 1; j <= N; ++j) {
                int cur = dp[j];
                if (s[i - 1] == s[N - j]) dp[j] = 1 + prev;
                else dp[j] = max(dp[j], dp[j - 1]);
                prev = cur;
            }
        }
        return dp[N];
    }
public:
    int minInsertions(string s) {
        return s.size() - longestPalindromeSubseq(s);
    }
};
  • class Solution {
        public int minInsertions(String s) {
            if (s.length() <= 1)
                return 0;
            StringBuffer sb = new StringBuffer(s);
            sb.reverse();
            String reverseStr = sb.toString();
            int longestCommonSubsequence = longestCommonSubsequence(s, reverseStr);
            return s.length() - longestCommonSubsequence;
        }
    
        public int longestCommonSubsequence(String str1, String str2) {
            int length1 = str1.length(), length2 = str2.length();
            int[][] dp = new int[length1 + 1][length2 + 1];
            for (int i = 1; i <= length1; i++) {
                char c1 = str1.charAt(i - 1);
                for (int j = 1; j <= length2; j++) {
                    char c2 = str2.charAt(j - 1);
                    if (c1 == c2)
                        dp[i][j] = dp[i - 1][j - 1] + 1;
                    else
                        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
            int commonLength = dp[length1][length2];
            return commonLength;
        }
    }
    
    ############
    
    class Solution {
        public int minInsertions(String s) {
            int n = s.length();
            int[][] f = new int[n][n];
            for (int i = n - 2; i >= 0; --i) {
                for (int j = i + 1; j < n; ++j) {
                    if (s.charAt(i) == s.charAt(j)) {
                        f[i][j] = f[i + 1][j - 1];
                    } else {
                        f[i][j] = Math.min(f[i + 1][j], f[i][j - 1]) + 1;
                    }
                }
            }
            return f[0][n - 1];
        }
    }
    
  • // OJ: https://leetcode.com/problems/minimum-insertion-steps-to-make-a-string-palindrome/
    // Time: O(N^2)
    // Space: O(N^2)
    class Solution {
    public:
        int minInsertions(string s) {
            int N = s.size();
            string t(s.rbegin(), s.rend());
            vector<vector<int>> dp(N + 1, vector<int>(N + 1));
            for (int i = 0; i <= N; ++i) {
                for (int j = 0; j <= N; ++j) {
                    if (i == 0 || j == 0) dp[i][j] = i + j;
                    else if (s[i - 1] == t[j - 1]) dp[i][j] = dp[i - 1][j - 1];
                    else dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1]);
                }
            }
            return dp[N][N] / 2;
        }
    };
    
  • # 1312. Minimum Insertion Steps to Make a String Palindrome
    # https://leetcode.com/problems/minimum-insertion-steps-to-make-a-string-palindrome/
    
    class Solution:
        def lps(self, start, end, s, mem):
            if start == end: return 1
            if start > end: return 0
            if mem[start][end]: return mem[start][end]
            
            mem[start][end] = 2 + self.lps(start+1, end-1, s, mem) if s[start] == s[end] else max(self.lps(start, end-1, s, mem), self.lps(start+1, end, s, mem))
            
            return mem[start][end]
        
        def minInsertions(self, s: str) -> int:
            n = len(s)
            mem = [[0]*n for _ in range(n)]    
            
            return n - self.lps(0, n-1, s, mem)
    
  • func minInsertions(s string) int {
    	n := len(s)
    	f := make([][]int, n)
    	for i := range f {
    		f[i] = make([]int, n)
    	}
    	for i := n - 2; i >= 0; i-- {
    		for j := i + 1; j < n; j++ {
    			if s[i] == s[j] {
    				f[i][j] = f[i+1][j-1]
    			} else {
    				f[i][j] = min(f[i+1][j], f[i][j-1]) + 1
    			}
    		}
    	}
    	return f[0][n-1]
    }
    
    func min(a, b int) int {
    	if a < b {
    		return a
    	}
    	return b
    }
    

All Problems

All Solutions