Grokking Dynamic Programming Interview in Python/

...

/

Longest Palindromic Substring

Longest Palindromic Substring

Let's solve the Longest Palindromic Substring problem using Dynamic Programming.

We'll cover the following...

Statement

Given a string s, find the length of its longest palindromic substring. The longest palindromic substring is a substring with maximum length that is also a palindrome. A phrase, word, or sequence is a palindrome that reads the same forward and backward.

For example, consider the string "bobgonoon". The palindromic substrings of "bobgonoon" are listed below:

Substring length

Substrings

1

"b", "o", "g", "n"

2

"oo"

3

"bob", "ono"

4

"noon"

The longest of them is "noon". Therefore, the length of the longest palindromic substring of "bobgonoon" is 4.

Constraints:

  • 1≤1 \leq s.length ≤900\leq 900

  • s consists of only lowercase letters.

Examples

No.

String

Longest Palindromic Substring Length

1

abcbq

3

3

dadxracecarpmadam

7

Try it yourself

Implement your solution in the following playground.

Press + to interact
Python
usercode > main.py
def find_lps_length(s):



    # Write your code here



    return -1
Longest Palindromic Substring

Note: If you clicked the "Submit" button and the code timed out, this means that your solution needs to be optimized in terms of running time.

Hint: Use dynamic programming and see the magic.

Solution

We will first explore the naive recursive solution to this problem and then see how it can be improved using the Palindromic Subsequence dynamic programming pattern.

Naive approach

A naive approach to this problem is to find all possible substrings, check whether each string is palindrome or not, and then select the string with the maximum length. A recursive solution that implements this approach is explained below:

  • Start two pointers from the start and end of the string.

  • If the characters at the two indexes match, recursively check if the substring between these two indexes is also a palindrome. If it's a palindrome, then it's the longest palindromic substring.

  • If the characters at the two indexes don't match, divide the problem into two subproblems by dropping a character from the start and end of the string. Call recursion on each subproblem to check if the strings are palindromes, and take the maximum length of the two substrings.

def find_lps_length(s):
    return find_lps_length_recursion(s, 0, len(s)-1)
def find_lps_length_recursion(s, start, end):
    # if both pointers are pointing to the same index
    if start==end:
        return 1
    # the characters at start and end indices match
    if s[start]==s[end]:
        substring_length = end - start + 1
        
        # if the substring length is 2 and it's also a palindrome
        if substring_length == 2:
            return 2
        
        # check whether the remaining string is a palindrome
        if substring_length == 2 + find_lps_length_recursion(s, start+1, end-1):
            return substring_length
    
    # skip one element either from the beginning or end and select the maximum resultant value
    return max(find_lps_length_recursion(s, start+1, end), find_lps_length_recursion(s, start, end-1))
# Driver code
def main():
    strings = ['abcbda', 'tworacecars', 'pqrssrqp', 'mnop', 'bbbbbbbbbbbbbbbbbbbb']
    
    # You can uncomment the line below and check how this recursive solution causes a time-out
    # strings.append('mwusjunybvgafxuhloqwfoizqkkqzilltjw')
    
    for i in range(len(strings)):
        print(i + 1, ".\t Input string: '", strings[i], "'", sep="")
        result = find_lps_length(strings[i])
        print("\t Length of the longest palindromic substring: ", result, sep="")
        print("-" * 100)
    
if __name__ == '__main__':
    main()
Longest Palindromic Substring using recursion

Note: Please observe that if you include the test case ...

Access this course and 1400+ top-rated courses and projects.