Longest Palindromic Substring

How to Solve Longest Palindromic Substring

Longest Palindromic Substring Introduction

The Longest Palindromic Substring problem asks us to return the longest palindromic substring in a given string s. This problem has an intuitive solution of expanding around the center but can often catch interviewees off-guard when faced with even-length palindromes.

Longest Palindromic Substring Problem

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

Example Inputs and Outputs

Example 1

Input: s = "babad"

Output: "bab"

Example 2

Input: s = "cbbd"

Output: "bb"

Longest Palindromic Substring Solutions

To find the longest palindromic substring in a given string, we can use a simple approach called "expand around center". Imagine you're reading the string from left to right, character by character. At each character, you can think of it as a potential center of a palindrome. To check if there's a palindrome centered around that character, you expand outward from the center and compare characters on both sides. If the characters match, you continue expanding until you find a mismatch or reach the boundaries of the string. By doing this for each character in the string, you can find the longest palindrome.

The tricky part is handling palindromes with even lengths. In that case, the center of the palindrome is between two characters rather than a single character. So, we treat each character and the space between two characters as potential centers and expand around them. By trying different centers and expanding around them, we can find the longest palindromic substring in the given string.

Python Code

def longestPalindrome(s):
    n = len(s)

# Edge case of string length 0 or 1
    if n <= 1:
        return s

start = 0
    maxLength = 1

# Helper function to expand around center
    def expandAroundCenter(left, right):
        while left >= 0 and right < n and s[left] == s[right]:
            left -= 1
            right += 1
        return right - left - 1

# Iterate through each character in the string
    for i in range(n):
        len1 = expandAroundCenter(i, i)
        len2 = expandAroundCenter(i, i + 1)
        currLen = max(len1, len2)

# Update longest
        if currLen > maxLength:
            maxLength = currLen
            start = i - (currLen - 1) // 2

# Return result
    return s[start:start + maxLength]

# Test case
input_string = "babad"
result = longestPalindrome(input_string)
print(result)

Time/Space Complexity Analysis