Teaching Kids Programming – Longest Palindromic Substring (Expand Around Center)

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.

For the bruteforce algorithm (with optimisation), you may refer to the post: Teaching Kids Programming – Longest Palindromic Substring (Optimised Bruteforce and Dynamic Programming Algorithm)

Longest Palindromic Substring (Expand Around Center)

There are two kinds of palindromes: the one with even number of characters such as “abba” or the one with odd number of characters such as “aba”. We then can bruteforce all possible centers.

There are O(N) centers and for each one, we need to expand around center which takes another O(N) – overall O(N^2).

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

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

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

–EOF (The Ultimate Computing & Technology Blog) —