How to Solve Longest Palindromic Substring

Written By
Adam Bhula

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
input_string = "babad"
result = longestPalindrome(input_string)

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.

About is a mock interview practice platform. We've hosted over 100K mock interviews, conducted by senior engineers from FAANG & other top companies. We've drawn on data from these interviews to bring you the best interview prep resource on the web.

We know exactly what to do and say to get the company, title, and salary you want.

Interview prep and job hunting are chaos and pain. We can help. Really.