Minimum Insertion To Form A Palindrome: A Dynamic Programming Problem

🙏
জয় শ্রী রাম
🕉

Algorithms and Data Structures: TheAlgorist.com
System Design: DistributedComputing.dev
Low Level Design: LowLevelDesign.io
Frontend Engineering: FrontendEngineering.io

Problem Statement:

Given a string str, the task is to find the minimum number of characters to be inserted to convert it to palindrome. Before we go further, let us understand with few examples:
ab: Number of insertions required is 1 i.e. bab
aa: Number of insertions required is 0 i.e. aa
abcd: Number of insertions required is 3 i.e. dcbabcd
abcda: Number of insertions required is 2 i.e. adcbcda which is same as number of insertions in the substring bcd(Why?).
abcde: Number of insertions required is 4 i.e. edcbabcde

Solution:

Pre-requisites:

Let the input string be str[l……h]. The problem can be broken down into three parts:
Find the minimum number of insertions in the substring str[l+1,…….h].
Find the minimum number of insertions in the substring str[l…….h-1].
Find the minimum number of insertions in the substring str[l+1……h-1].

So, the minimum number of insertions in the string str[l…..h] can be given as:

minInsertions(str[l+1…..h-1]) if str[l] is equal to str[h]
min(minInsertions(str[l…..h-1]), minInsertions(str[l+1…..h])) + 1 otherwise

More detailed explanation:
Let's imagine matching the characters of the string like a palindrome, from the beginning and the end with 2 pointers at index i and index j.
We may encounter 2 scenarios:

The character at index i matches the character at index j.
In this case we just increase the pointer i and decrease the pointer j, i.e, i++ and j-- respectively.
The minimum insertion required for string[i...j] will be same as that for string[(i + 1)...(j - 1)].
The character at index i don't match the one at index j.

In this case we have 2 options:
1. Insert one character at index (j + 1) to match the character at i.
  dp[i][j] = dp[i + 1][j] + 1. Basically we are disregarding the character at index i, since we would be inserting a character at index (j + 1) matching that character at index i. So, we are interested in knowing value of dp[i + 1][j].
2. Insert one character at (i - 1) to match the character at j.
  dp[i][j] = dp[i][j - 1] + 1
Since we are interested in getting the min value: dp[i][j] = min(dp[i + 1][j] + 1, dp[i][j - 1] + 1)

Java Code:

Python Code:

Longest Palindromic Subsequence based solution:

I cannot emphasize enough on how much important it is to be able to reuse your existing knowledge in solving various problems. This quality makes a problem solver stand out of the crowd. This is true not only for interview preparation, but this is also true in professional life. What makes a great software engineer great is the quality of building reusable and extensible components as well as being able to reuse other software component, whenever possible, without reinventing the wheel. If you have followed all other previously discussed problems, you might have already figured that this problem is very subtle application of one of those problems, and how easily that makes the solution for this problem. The problem that we are talking about is Longest Palindromic Subsequence. If we have a string with length n and the length of the longest palindromic subsequence is m then (n - m) characters have no matching characters and we need to insert one instance of each of those characters in proper order to make the entire string palindrome. So, minimum insertion required to make the whole string palindrome = length of the string - length of longest palindromic subsequence.

My request to you is to take each and every core concept and problem we discuss very seriously and have a strong grasp of all of them, since I have picked each and every problem very thoughtfully and each and every one of them has a purpose. You will see your effort paying off in tech interviews, competitive programming, and class tests / semester exams.

During interviews, for most of us our stress levels go up. I would suggest you to keep your calm and try to do as many observations as possible in the given problem. In order to reuse your knowledge of solving other problems and classic algorithm problems you need to do the proper observation. You definitely need to think out loud, but please take some time to make all the necessary observations with full concentration. Feel free to take a minute to do this and let your interviewer know that you just taking some time to figure out the key points.

Java Code:

Python Code:

Longest Common Subsequence based Solution:

Now we will be reusing our knowledge of solving another previously discussed problem to solve this one.

In a Palindrome, you encounter the matching characters from beginning and ending (i.e, from left and right) in the same order. If we compute Longest Common Subsequence of the given string and the reverse of the given string we would actually get the subsequence that is palindrome. The rest of the characters in the given string do not contribute to palindrome property since they have no matching characters. So we just need to insert those matching characters in proper order to make the entire given string a palindrome. This means the difference between the length of the given string and the length of the longest common subsequence is the answer we are looking for.

Java Code:

Python Code:

Instructor:

Abhishek Dey

Senior SDE | Chief Architect

Microsoft | University of Florida

View LinkedIn profile

If you have any feedback, please use this form: https://thealgorists.com/Feedback.