How can we find the length of longest palindromic string in string given by dp?

#1

can we solve it by using dynamic programming if yes then how?

#2

Hello @amanm2292,
Yes, this problem can be solved using DP.

Let’s understand this using an example:
Suppose there is a string of length 7.

  1. We will divide the strings into two sub strings recursively and check if they are palindrome.
    This satisfies, Optimal Substructure:

                       (0,7)
             (0,6)       (1,7)
          (0,5) (1,6) (1,6) (2,7)
                 ....so on

  2. You can observe, the substructures are repeating such as (1,6).
    This satisfies, substructure overlapping.

As, this question satisfies the both the properties.
Hence, it is a problem of DP.

You can refer to this video.

Hope, this would help.
Give a like, if you are satisfied.

#3

Hello @amanm2292,
You have not replied to this thread for 4 days.
Please, mark it as resolved if you have solved it.
Else, let me know if you are facing any problem.

#4

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.