Katkat
Back

Find longest palindromic substring

MetaMachine Learning Engineer · Onsite
MediumMachine Learning EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to optimize string processing algorithms, specifically moving from a brute-force approach to an efficient expansion-based technique for identifying palindromic patterns.

Problem Statement

Given a string s, return the longest palindromic substring in s. A palindrome reads the same forward and backward. If there are multiple palindromic substrings of the same maximum length, returning any one of them is acceptable.

Function Signature

def longestPalindrome(s: str) -> str:

Constraints

  • 1 <= s.length <= 1000
  • s consists of only digits and English letters.

Examples

Example 1: Input: s = "babad" Output: "bab" Explanation: "aba" is also a valid answer.

Example 2: Input: s = "cbbd" Output: "bb"

Edge Cases

  • Single character strings (e.g., "a").
  • Strings where no palindrome longer than 1 exists (e.g., "abc").
  • Strings consisting entirely of the same character (e.g., "aaaa").

Hints

Hint 1

Consider that a palindrome mirrors around its center; how many possible centers are there in a string of length N?

Hint 2

For each possible center, expand outwards as long as the characters match and remain within the string boundaries.

Hint 3

Remember to handle both odd-length palindromes (centered on a single character) and even-length palindromes (centered between two characters).

Follow-up questions

  • What is the time and space complexity of your current solution, and can you achieve O(N) time complexity using Manacher's Algorithm?
  • How would you modify this solution if the input string was extremely large and needed to be processed as a stream?
  • How does the performance of this algorithm change if the string contains multi-byte Unicode characters instead of standard ASCII/English letters?