1312. Minimum Insertion Steps to Make a String Palindrome
Problem Description
The task is to make a given string s
a palindrome by inserting any number of characters at any position in the string. The objective is to achieve this with the minimum number of insertions possible. A palindrome is a word, number, phrase, or other sequences of characters that reads the same forward and backward, ignoring spaces, punctuation, and capitalization.
Intuition
To solve this problem, we can use dynamic programming. The core idea is to build a solution using the answers to smaller subproblems. These subproblems involve finding the minimum number of insertions for all substrings of the given string and building upon those to arrive at the final answer.
We can define our subproblem as f(i, j)
, which is the minimum number of insertions to make the substring s[i...j]
a palindrome. Therefore, f(0, n-1)
(where n
is the length of the string) will eventually be our answer for the whole string s
.
If the characters at the position i
and j
are the same, no insertion is needed, and f(i, j)
will be the same as f(i+1, j-1)
ā the number of insertions needed for the substring without these two matching characters. However, if they do not match, we have to do an insertion either at the beginning or the end of the substring. This means we have two options: either insert a character matching s[j]
before i
or insert a character matching s[i]
after j
. Therefore, we'll take the minimum of f(i+1, j)
and f(i, j-1)
and add one (for the insertion we've made). We do this for all possible substrings starting from the end of the string and moving backward, which finally gives us the minimum number of insertions needed to make the entire string a palindrome.
The Python solution provided implements this dynamic programming approach. It utilizes a 2D array f
where f[i][j]
holds the minimum number of insertions needed for the substring s[i...j]
. We iterate through the string in reverse, gradually building up the solution for the entire string and returning f[0][-1]
, which represents the minimum number of insertions needed for the whole string s
.
Learn more about Dynamic Programming patterns.
Solution Approach
The solution to this problem applies dynamic programming because a direct approach would involve checking every possible insertion, leading to an inefficient exploration of the problem space. Dynamic programming, however, allows us to solve the problem more efficiently by breaking it down into overlapping subproblems and building up the answer.
Here's a step-by-step explanation of the dynamic programming solution provided in the Reference Solution Approach:
-
We use a 2D array
f
with dimensionsn
byn
, wheren
is the length of the strings
.f[i][j]
will represent the minimum number of insertions required to make the substrings[i...j]
a palindrome. -
We initialize our dp array
f
with zeros because ifi
equalsj
, the substring is already a palindrome, and no insertions are needed. -
The main process occurs in a nested loop. We first iterate over
i
in reverse, starting fromn-2
down to0
. The reason for starting atn-2
is that the last character does not need any insertions to become a palindrome; it already is one on its own. -
For each
i
, we then iterate overj
fromi+1
ton-1
. This loop considers all substrings that start at indexi
and end at indexj
. -
Inside the nested loops, we check if the characters at index
i
andj
are the same.-
If
s[i]
is equal tos[j]
, no additional insertions are needed to pair them up, sof[i][j]
is set equal tof[i+1][j-1]
(the minimum insertions needed for the inside substring). -
If
s[i]
is not equal tos[j]
, we must insert a character. We can choose to aligns[i]
with some character to the right or to aligns[j]
with a character to the left. Therefore,f[i][j]
is the minimum off[i+1][j]
andf[i][j-1]
(the solutions to subproblems considering one side extended), plus one for the current insertion.
-
-
At the completion of the loops,
f[0][-1]
contains the answer. It represents the minimum number of insertions needed for the whole string, because it refers to the subproblem considering the entire strings[0...n-1]
.
By using dynamic programming, we avoid re-computing solutions to subproblems, which makes for an efficient solution. The Reference Solution Approach leverages this overlapping of subproblems and optimal substructure properties common in dynamic programming problems.
This algorithm has a time complexity of O(n^2)
due to the nested for loops iterating over all substrings, and a space complexity of O(n^2)
as well for storing the dp array. While the space complexity could be a concern for very long strings, the quadratic time complexity is a significant improvement over any naive approach.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider a short example with the string s = "abca"
. We want to find the minimum number of insertions required to make s
a palindrome.
-
Initialize a 2D array
f
with dimensions 4x4, with all values set to 0, since the length of the strings
is 4.0 1 2 3 0 0 1 0 2 0 3 0 -
Fill in the dp array
f
starting fromi = 2
down to0
. We need to loop fromj = i+1
to3
. We ignore cases wherei == j
because those are already palindromes. -
Start with
i = 2
andj = 3
:s[2] = "c"
,s[3] = "a"
. They do not match, so we need one insertion. We take the minimum fromf[2+1][3]
andf[2][3-1]
, which are both0
at the moment, so after adding 1,f[2][3] = 1
.0 1 2 3 0 0 1 0 2 0 1 3 0 -
Move to
i = 1
andj = 2
:s[1] = "b"
,s[2] = "c"
. They do not match, so we take the minimum off[1+1][2]
andf[1][2-1]
, with an extra insertion. Sincef[2][2]
andf[1][1]
are0
, we setf[1][2]
to1
. -
For
i = 1
andj = 3
, compares[1]
tos[3]
, which are "b" and "a". They're different, sof[1][3]
is the minimum off[1+1][3]
andf[1][3-1]
, which are1
and1
at this point, plus one for the insertion; we getf[1][3] = 2
. -
Now for
i = 0
andj = 1
:s[0] = "a"
,s[1] = "b"
. They're different, so we setf[0][1]
to the minimum off[0+1][1]
orf[0][1-1]
plus 1, which equals1
. -
For
i = 0
,j = 2
, we take the minimum off[1][2]
andf[0][1]
. Both are1
currently, sof[0][2] = 2
. -
Finally, for
i = 0
,j = 3
, we compares[0]
withs[3]
, which are the same. So, we setf[0][3]
tof[1][2]
, which is1
.
The final dp array f
looks like this:
| | 0 | 1 | 2 | 3 | |---|---|---|---|---| | 0 | 0 | 1 | 2 | 1 | | 1 | | 0 | 1 | 2 | | 2 | | | 0 | 1 | | 3 | | | | 0 |
The top right cell f[0][3]
gives us the minimum number of insertions needed, which is 1
. In this case, we can insert a "b" at the end of the string to get "abcba", which is a palindrome.
This example demonstrates the procedure described in the solution approach, illustrating the steps taken to fill the dp array and find the minimum number of insertions to make the string s
a palindrome.
Solution Implementation
1class Solution:
2 def minInsertions(self, s: str) -> int:
3 # Length of the input string
4 length = len(s)
5
6 # dp (Dynamic Programming) table where dp[i][j] will hold the
7 # minimum number of insertions needed to make s[i...j] a palindrome
8 dp = [[0] * length for _ in range(length)]
9
10 # Loop backwards through the string so that we can solve
11 # for all the smaller subproblems first
12 for i in range(length - 2, -1, -1):
13 for j in range(i + 1, length):
14 # If the characters at position i and j are the same,
15 # no more insertions are required here since it already
16 # contributes to a palindrome
17 if s[i] == s[j]:
18 dp[i][j] = dp[i + 1][j - 1]
19 else:
20 # If the characters are different, we need one more
21 # insertion. We can insert either at the beginning
22 # or at the end of the substring. We choose the option
23 # that requires fewer insertions, hence the min function.
24 dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + 1
25
26 # The top-right corner of the dp table contains the answer
27 # for the whole string, which is what we return.
28 return dp[0][-1]
29
1class Solution {
2 public int minInsertions(String s) {
3 int length = s.length();
4 int[][] dp = new int[length][length]; // Using dp array to store minimum insertion results
5
6 // Iterating in reverse order from second last character to the beginning
7 for (int i = length - 2; i >= 0; --i) {
8 // Iterating from the character just after i up to the end of the string
9 for (int j = i + 1; j < length; ++j) {
10 // If the characters at i and j match, no insertion is needed; carry over the value from the previous subproblem
11 if (s.charAt(i) == s.charAt(j)) {
12 dp[i][j] = dp[i + 1][j - 1];
13 } else {
14 // If the characters do not match, find the minimum insertion from the two adjacent subproblems and add 1
15 dp[i][j] = Math.min(dp[i + 1][j], dp[i][j - 1]) + 1;
16 }
17 }
18 }
19
20 // The top-right corner of the DP matrix contains the answer for the whole string
21 return dp[0][length - 1];
22 }
23}
24
1class Solution {
2public:
3 int minInsertions(string s) {
4 int n = s.size();
5 vector<vector<int>> dp(n, vector<int>(n, 0)); // Create a DP table with `n` rows and `n` columns initialized to 0
6
7 // Fill the DP table starting from the bottom right and moving to the top left
8 for (int startIdx = n - 2; startIdx >= 0; --startIdx) { // Start from second last character since last character doesn't need any insertion
9 for (int endIdx = startIdx + 1; endIdx < n; ++endIdx) { // End index ranges from the character after startIdx to the end of the string
10 if (s[startIdx] == s[endIdx]) {
11 // No insertion needed if characters at startIdx and endIdx are the same,
12 // we just take the value from the diagonal entry before the next iteration
13 dp[startIdx][endIdx] = dp[startIdx + 1][endIdx - 1];
14 } else {
15 // If characters are not the same, we take the minimum insertions needed
16 // from the positions right after startIdx or right before endIdx and add one
17 dp[startIdx][endIdx] = min(dp[startIdx + 1][endIdx], dp[startIdx][endIdx - 1]) + 1;
18 }
19 }
20 }
21
22 // The minimum number of insertions needed to make the string `s` a palindrome
23 // is stored in the top right corner of the DP table
24 return dp[0][n - 1];
25 }
26};
27
1// Define a function to calculate the minimum number of insertions to make a string a palindrome
2function minInsertions(s: string): number {
3 const n: number = s.length;
4 // Create a DP table with `n` rows and `n` columns initialized to 0
5 const dp: number[][] = Array.from({ length: n }, () => Array(n).fill(0));
6
7 // Loop to fill the DP table starting from the bottom right and moving to the top left
8 for (let startIdx = n - 2; startIdx >= 0; --startIdx) { // Start from the second-last character.
9 for (let endIdx = startIdx + 1; endIdx < n; ++endIdx) { // Loop over the remaining characters to the right.
10 if (s[startIdx] === s[endIdx]) {
11 // If characters at startIdx and endIdx are the same,
12 // no insertions are needed so take value from the diagonal entry before the next iteration.
13 dp[startIdx][endIdx] = dp[startIdx + 1][endIdx - 1];
14 } else {
15 // If characters are different, find the minimum of the insertions needed
16 // after startIdx or before endIdx and increment by one.
17 dp[startIdx][endIdx] = Math.min(dp[startIdx + 1][endIdx], dp[startIdx][endIdx - 1]) + 1;
18 }
19 }
20 }
21
22 // Return the minimum number of insertions needed to make the string `s` a palindrome,
23 // which is stored in the top right corner of the DP table.
24 return dp[0][n - 1];
25}
26
Time and Space Complexity
The given Python code snippet is designed to find the minimum number of insertions needed to make the input string a palindrome. It uses dynamic programming to accomplish this task. The analysis of time and space complexity is as follows:
Time Complexity:
The time complexity of the code is O(n^2)
, where n
is the length of the input string s
. This is because there are two nested loops:
- The outer loop runs backwards from
n-2
to0
, which contributes to anO(n)
complexity. - The inner loop runs from
i + 1
ton
, which also contributes toO(n)
complexity when considered with the outer loop.
Since each element f[i][j]
of the DP matrix f
is filled once and the amount of work done for each element is constant, the overall time complexity is the product of the two O(n)
complexities.
Space Complexity:
The space complexity of the code is also O(n^2)
. This is because a two-dimensional array f
of size n * n
is created to store intermediate results of the dynamic programming algorithm.
So, both the space and time complexity are quadratic in terms of the length of the input string.
Learn more about how to find time and space complexity quickly using problem constraints.
Which algorithm should you use to find a node that is close to the root of the tree?
Recommended Readings
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!