Minimum Insertion Steps to Make a String Palindrome - Solution & Explanation
Problem Statement
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 <= 500sconsists of lowercase English letters.
Approach Overview
Problem Overview: Given a string s, compute the minimum number of characters you must insert anywhere in the string so the final string becomes a palindrome. Insertions can be made at any position, but existing characters cannot be removed or reordered.
Approach 1: Dynamic Programming (Longest Palindromic Subsequence) (Time: O(n^2), Space: O(n^2))
The key observation: the minimum insertions required equals n - LPS, where LPS is the length of the Longest Palindromic Subsequence. A subsequence that is already palindromic does not require changes; you only insert characters to mirror the missing parts. Compute LPS by finding the Longest Common Subsequence between the string and its reverse. Use a 2D DP table where dp[i][j] stores the LCS length for prefixes of the original and reversed string. The final answer becomes n - dp[n][n]. This approach is stable, easy to reason about, and widely expected in interviews involving dynamic programming and string problems.
Approach 2: Recursion with Memoization (Time: O(n^2), Space: O(n^2))
Work directly on the palindrome property using two pointers. Define a recursive function on substring indices (i, j). If s[i] == s[j], both characters can stay in the palindrome, so recurse on (i+1, j-1). If they differ, you must insert a matching character on either side, which means taking 1 + min(f(i+1, j), f(i, j-1)). Memoize results in a 2D cache to avoid recomputation of overlapping subproblems. This formulation mirrors how palindromes are built from both ends and is a natural application of dynamic programming over substrings.
Recommended for interviews: The Longest Palindromic Subsequence transformation is usually the expected explanation because it reduces the problem to a well-known DP pattern. Mentioning the recursive two‑pointer formulation shows deeper understanding of palindrome structure, but implementing the LPS DP tends to be cleaner and easier to debug under time pressure.
Approach 1: Approach 1: Dynamic Programming (Longest Palindromic Subsequence)
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.
Complexity
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.
Approach 2: Approach 2: Recursion with Memoization
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.
Complexity
Time Complexity: O(n^2)
Space Complexity: O(n^2) due to the memoization table.
Approach 3: Default Approach
Try this approach in the editor →Complexity Comparison
| 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) |
| Default Approach | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming (Longest Palindromic Subsequence via LCS) | O(n^2) | O(n^2) | Standard interview solution; reliable for strings up to typical DP constraints |
| Recursion with Memoization (Two-Pointer Substring DP) | O(n^2) | O(n^2) | When reasoning directly about palindrome construction from both ends |
Video Solution
DP 29. Minimum Insertions to Make String Palindrome • take U forward • 267,772 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Minimum Insertion Steps to Make a String Palindrome easy or hard?
Minimum Insertion Steps to Make a String Palindrome Python/Java solution
How to solve Minimum Insertion Steps to Make a String Palindrome in O(n)?
What is the best approach for Minimum Insertion Steps to Make a String Palindrome?
Is Minimum Insertion Steps to Make a String Palindrome asked at Google/Amazon/Meta?
What data structure is used in Minimum Insertion Steps to Make a String Palindrome?
What is the time complexity of Minimum Insertion Steps to Make a String Palindrome?
Ready to solve this problem?
Practice Minimum Insertion Steps to Make a String Palindrome with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor