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.
A 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 do not 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".
Constraints:
1 <= s.length <= 500s consists of lowercase English letters.This approach utilizes dynamic programming to find the longest palindromic subsequence in the given string. The minimum number of insertions required is the difference between the length of the string and this subsequence. The idea is to consider characters from both ends of the string and make decisions accordingly using a DP table.
The function uses a 2D array dp where dp[i][j] represents the minimum insertions required to make the substring s[i...j] a palindrome. We iterate over increasing lengths of substrings and decide whether to skip or keep certain characters based on whether they match.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2), where 'n' is the length of the string. This is due to the nested loops filling the DP table.
Space Complexity: O(n^2), as it uses a two-dimensional array for the DP table.
This approach leverages a recursive function to explore all possibilities, but uses memoization to cache results of previously computed subproblems. This reduces redundant calculations.
This C solution uses a recursive function solve which calculates the minimum insertions needed for a substring. It includes memoization to store intermediate results in a 2D array, avoiding redundant calculations.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2)
Space Complexity: O(n^2) due to the memoization table.
| Approach | Complexity |
|---|---|
| Approach 1: Dynamic Programming (Longest Palindromic Subsequence) | Time Complexity: O(n^2), where 'n' is the length of the string. This is due to the nested loops filling the DP table. |
| Approach 2: Recursion with Memoization | Time Complexity: O(n^2) |
DP 29. Minimum Insertions to Make String Palindrome • take U forward • 189,043 views views
Watch 9 more video solutions →Practice Minimum Insertion Steps to Make a String Palindrome with our built-in code editor and test cases.
Practice on FleetCode