Longest Palindromic Substring

StringDynamic Programming

MediumLeetCode #5

30 min

Problem Statement

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

Example

Example 1:

Input: s = "babad"

Input: "babad"

Longest Palindromic Substring: "bab"

Output: "bab"

Explanation: "aba" is also a valid answer.

Solution (Expand From Center)

A common and efficient approach is to "expand from center". We iterate through each character of the string and treat it as the center of a potential palindrome. We then expand outwards from that center to find the longest palindrome.

Algorithm Steps

Initialize an empty string to store the longest palindromic substring found so far.
Iterate through the input string with an index i.
For each index i, consider two cases for the center of the palindrome:
An odd length palindrome centered at i.
An even length palindrome centered between i and i+1.
For each case, expand outwards from the center(s) as long as the characters match and you are within the bounds of the string.
If a new longer palindrome is found, update the result.
After iterating through the entire string, return the result.

Input (s):

Longest Palindrome:

Start.

Longest Palindromic Substring Solution


class Solution:
    def longestPalindrome(self, s: str) -> str:
        res = ""
        resLen = 0
        
        for i in range(len(s)):
            # odd length
            l, r = i, i
            while l >= 0 and r < len(s) and s[l] == s[r]:
                if (r - l + 1) > resLen:
                    res = s[l:r+1]
                    resLen = r - l + 1
                l -= 1
                r += 1
            
            # even length
            l, r = i, i + 1
            while l >= 0 and r < len(s) and s[l] == s[r]:
                if (r - l + 1) > resLen:
                    res = s[l:r+1]
                    resLen = r - l + 1
                l -= 1
                r += 1
                
        return res