MEDIUM
DATA STRUCTURES AND ALGORITHMS

# How to Solve Longest Palindromic Substring

Written By

## 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.

``````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
result = longestPalindrome(input_string)
print(result)``````

#### Time/Space Complexity Analysis

• Time Complexity: O(n²), as we have nested loops iterating through the string. The outer loop runs for each character in the string, and the inner loop expands around the center to find palindromes. In the worst case, we may need to expand on both sides for every character, resulting in a quadratic time complexity.
• Space Complexity: O(1), as we only use a constant amount of extra space to store variables and temporary values.