Data structure and algorithm is a wide concept and getting better at it requires lots of theoretical and practical knowledge. While preparing for an interview or an exam, getting doubts related to DSA concepts is totally understandable.
Today we will look at one particular concept – How To Print Longest Palindromic Subsequence (LPS), to help you with all your doubts.
The LPS is nothing but a long string that spells the same element both forward and backward. To help you understand this concept much better, we will provide you a whole guide starting from definitions, example sequence and of course about top-down and the bottom-up dynamic programming approaches.
We will also be covering the basics of the Dynamic programming approach to resolve a “how to print a longest palindromic subsequence” problem. Through this programming method, you can also solve box stacking problems which is a longest increasing subsequence problem.
Without much ado, let’s take a glance!
What is a longest palindromic subsequence?
The longest string of characters in a string that spells the same thing both forward and backward is known as a longest palindromic subsequence.
Let’s separate them for better understanding. So basically,
Subsequence: A subsequence is a sequence that is created by removing some (potentially zero) components from the main sequence. It is taken from an array of elements. To put it another way, it’s a sequence that was obtained from the original sequence without altering the relative order of the pieces. For instance, “bdf” comes after the sequence “abcdefg.” Additionally, we view xyz as a part of the same xyz sequence. As a result of the original sequence’s a and b being in a different order, abd is not a subsequence of baed.
Palindrome: On the other hand, any sequence that can be read the same way both forward and backward is called a palindrome. For instance, while abca is not a palindrome sequence, byzzyb and abcba are.
Now let us look at what Dynamic programming is and how it is associated with a longest palindromic subsequence.
What is Dynamic programming?
Dynamic programming is a technique that divides the issues into smaller ones and saves the answer for use at a later time without having to recalculate it. The optimal substructure property refers to the optimization of the subproblems in order to maximize the overall solution. If a solution does exist, dynamic programming ensures that the best solution will be found.
Dynamic programming, stated simply, is a method for resolving complex issues by first deconstructing them into a set of simpler subproblems, resolving each subproblem only once, and then storing the solutions to prevent calculations from being repeated.
As we know, Dynamic algorithms are driven by a problem-wide optimization, in contrast to algorithms that focus on local optimization. Dynamic algorithms employ the results of a smaller sub-problem and then attempt to optimize a larger sub-problem, in contrast to divide and conquer algorithms, where solutions are merged to obtain an overall solution.
Additionally, Memorization is a technique used by dynamic algorithms to retain the results of previously solved subproblems. Moreover, Dynamic programming approach an be used to solve problems like,
- Fibonacci number series
- Knapsack problem
- Tower of Hanoi
- Shortest path by Dijkstra
- Project scheduling
- Box stacking
What are the types of Dynamic programming?
The two types of Dynamic programming are,
- Top-down
- Bottom-up
Top-down method
While the bottom-up strategy uses the tabulation method, the top-down approach uses memorization. Recursion plus caching in this case equals memorizing. While caching entails keeping the interim results, recursion entails calling the method directly. Some of the pros of this method are,
- It is really simple to comprehend and put into practice.
- The subproblems are only resolved when necessary.
- It’s simple to debug.
The disadvantage is that, It makes use of the recursion approach, which utilizes additional call stack memory. Occasionally, the stack overflow issue will occur due to excessive recursion. Moreover, It uses up more memory, which lowers performance as a whole.
Bottom-up method
The bottom-up dynamic programming method is implemented using the tabulation technique. The recursion is eliminated while still solving the same kind of issues. The stack overflow problem and the overhead of the recursive routines go away if the recursion is removed.
Using this method of tabulation, we resolve the issues and matrix the solutions. The advantage is that it saves up memory and eliminates recursion.
How to print longest palindromic subsequence using dynamic programming?
To understand it better, let us take a sample problem and see how one can print the longest palindromic subsequence.
Take string “CBBCDCBBC”, as an example. For this string, the longest palindromic subsequence is “BBCBB”. A naive approach would filter out the longest palindromic subsequence from the above string. But, this method comes with exponential time complexity.
This is where the dynamic programming approach best fits and we look at the Bottom-Up DP method.
Firstly, define the DP state that is , dp[i][j] (it denotes the length of the LPS). Then you can use the gap method to fill the dp table.
How so?
- Name the string length of nn as ss
- Then fill the dp table for all the substring with gap then with gap 1 until the gap of n-1 n-1.
- Then declare a 2-D array dpdp of size n\times nn x n
- Declare a variable, say ii, and initialize it to 0, then iterate for gap = 0 gap=0 to gap = n-1 gap=n1.
- Follow these steps as you iterate for j=gapj=gap to j=n-1j=n1:
- According to the state transitions mentioned above, fill in the dp[i][j].
- Add one to the number I i.e. i++
- The length of the LPS for the string s[0…n-1]s[0…n1], or the original string, is now contained in dp[0][n-1].
Final thoughts
We hope you have learned about how to print longest palindromic subsequence, a thorough insight of dynamic programming approach along with its type and an example problem employing bottom-up approach.
