Katkat
Back

Find the Longest Palindromic Substring

eBaySoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

Implement an algorithm to find the longest palindromic substring in a given string, breaking ties by selecting the earliest occurrence and properly handling empty inputs.

Problem Statement

Given a string s, find and return the longest contiguous substring that reads the same forwards and backwards (a palindrome).

If there are multiple palindromic substrings that share the maximum length, return the one that occurs earliest in the string (i.e., has the smallest starting index). If the input string is empty, return an empty string "".

Function Signature

def longest_palindromic_substring(s: str) -> str:
    pass

Input & Output Format

  • Input: A single string s consisting of printable ASCII characters.
  • Output: A string representing the longest palindromic substring.

Constraints

  • 0 <= len(s) <= 1000
  • s consists of English letters, digits, and standard symbols.

Examples

Example 1

Input: s = "babad"
Output: "bab"
Explanation: Both "bab" and "aba" are palindromic substrings of length 3. "bab" begins at index 0, while "aba" begins at index 1. Because "bab" starts earlier, it is the correct answer.

Example 2

Input: s = "cbbd"
Output: "bb"
Explanation: The longest palindromic substring is "bb", which has a length of 2.

Example 3

Input: s = ""
Output: ""
Explanation: The input is empty, so the output is an empty string.

Edge Cases

  • Empty string: s = "" should return "".
  • Single character string: s = "a" should return "a".
  • No multi-character palindrome exists: s = "abcdef" should return "a" (the first single-character palindrome).

Hints

Hint 1

A palindrome can be centered on a single character (odd length) or between two characters (even length).

Hint 2

Iterate through all possible centers from left to right, expanding outward as long as the surrounding characters match.

Hint 3

To satisfy the tie-breaking rule, only update your tracked maximum palindrome when an expanded palindrome is strictly longer than the current best.

Follow-up questions

  • How can you optimize this problem to achieve linear O(n) time complexity using Manacher's Algorithm?
  • How would your approach adapt if the input string is very large and streamed in chunks rather than provided all at once in memory?
  • What changes would be required if the problem asked for the total number of distinct palindromic substrings instead of just the longest?