Teaching Kids Programming – Longest Palindromic Substring (Optimised Bruteforce and Dynamic Programming Algorithm)

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a string s, return the longest palindromic substring in s.

Example 1:
Input: s = “babad”
Output: “bab”
Explanation: “aba” is also a valid answer.

Example 2:
Input: s = “cbbd”
Output: “bb”

Constraints:
1 <= s.length <= 1000
s consist of only digits and English letters.

Hints:
How can we reuse a previously computed palindrome to compute a larger palindrome?
If “aba” is a palindrome, is “xabax” a palindrome? Similarly is “xabay” a palindrome?
Complexity based hint:
If we use brute-force and check whether for every start and end position a substring is a palindrome we have O(n^2) start – end pairs and O(n) palindromic checks. Can we reduce the time for palindromic checks to O(1) by reusing some previous computation.

Naive Bruteforce Algorithm to Get the Longest Palindrome Substring

The first solution would be to bruteforce the substrings in O(N^2) time. And for each substring, we check if it is a palindrome which takes O(N) time. The overall time complexity is O(N^3).

1
2
3
4
5
6
7
8
9
10
11

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        L = R = 0
        for i in range(n):
            for j in range(i, n):
                if s[i:j+1] == s[i:j+1][::-1]:
                    if j - i > R - L:
                        L = i
                        R = j
        return s[L:R+1]

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        L = R = 0
        for i in range(n):
            for j in range(i, n):
                if s[i:j+1] == s[i:j+1][::-1]:
                    if j - i > R - L:
                        L = i
                        R = j
        return s[L:R+1]

Please note that the array/string slicing in Python also takes O(N) time. Here, we store the left and right index of the longest palindrome substring.

Optimised Bruteforce Algorithm to Get the Longest Palindrome Substring

We can slightly improve the bruteforce, by reverse the inner check, and break once we have found a palindrome. No need to continue as the rest of the inner loop gives a shorter substring.

1
2
3
4
5
6
7
8
9
10
11
12

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        L = R = 0
        for i in range(n):
            for j in range(n - 1, i - 1, -1):
                if s[i:j+1] == s[i:j+1][::-1]:
                    if j - i > R - L:
                        L = i
                        R = j
                    break
        return s[L:R+1]

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        L = R = 0
        for i in range(n):
            for j in range(n - 1, i - 1, -1):
                if s[i:j+1] == s[i:j+1][::-1]:
                    if j - i > R - L:
                        L = i
                        R = j
                    break
        return s[L:R+1]

Time complexity is still O(N^3).

Dynamic Programming Algorithm to Check if a Substring is a Palindrome

Checking palindrome substring is expensive but we can pre-compute this in O(N^2) using Dynamic Programming – which we can do it Top Down or Bottom Up.

The Top Down is via Recursion and Memoization. It is based on the following observations. Given represent if substring from index i to index j inclusive is a palindrome:

if i==j
if i+1==j
Otherwise,

Recursion and memoziation implementation via the @cache keyword to remember the values that we have calculated. Total states where N is the length of the string.

1
2
3
4
5
6
7
8
9

@cache
def f(i, j):
    if i == j:
        return True
    if i + 1 == j:
        return s[i] == s[j]
    if i > j:
        return False
    return s[i] == s[j] and f(i + 1, j - 1)

@cache
def f(i, j):
    if i == j:
        return True
    if i + 1 == j:
        return s[i] == s[j]
    if i > j:
        return False
    return s[i] == s[j] and f(i + 1, j - 1)

The f function (Top Down DP) can replace the O(N) palindrome check direclty however it is still not fast enough as there is Recursion function call overhead. And we can improve this by Bottom Up Dynamic Programming which stores the F values in a two dimensional array.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
 
        F = [[True for _ in range(n)] for _ in range(n)]
        for i in range(n - 2, -1, -1):
            for j in range(i, n):
                F[i][j] = s[i] == s[j] and F[i + 1][j - 1]
        
        L = 0
        R = 0
        for i in range(n):
            for j in range(n - 1, i - 1, -1):
                if F[i][j]:
                    if j - i > R - L:
                        L = i
                        R = j
                    break
        return s[L:R+1]

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)

        F = [[True for _ in range(n)] for _ in range(n)]
        for i in range(n - 2, -1, -1):
            for j in range(i, n):
                F[i][j] = s[i] == s[j] and F[i + 1][j - 1]
        
        L = 0
        R = 0
        for i in range(n):
            for j in range(n - 1, i - 1, -1):
                if F[i][j]:
                    if j - i > R - L:
                        L = i
                        R = j
                    break
        return s[L:R+1]

The time/space complexity is quadratic.

Finding the Longest Palindrome Substring can also be solved using another approach: Teaching Kids Programming – Longest Palindromic Substring (Expand Around Center)

–EOF (The Ultimate Computing & Technology Blog) —