Longest Palindromic Substring
Problem Description
Given a string s, return the longest palindromic substring.
Example 1:
Input: s = "racecar"
Output: "racecar"
Example 2:
Input: s = "cbbd"
Output: "bb"
Note: When multiple palindromes share the maximum length, any valid answer is accepted. The test cases below have unique answers.
DE Shaw Tier 2 — LC 5.
Two approaches:
1. Expand around center O(n^2) time O(1) space: for each index, expand odd and even palindromes.
2. DP O(n^2) time and space: dp[i][j] = true if s[i..j] is palindrome.
For interviews, mention Manacher's O(n) exists but expand-around-center is usually sufficient.
Example Test Cases
Example 1
Input: ["racecar"]
Expected: "racecar"
Example 2
Input: ["cbbd"]
Expected: "bb"
Example 3
Input: ["a"]
Expected: "a"
Example 4
Input: ["banana"]
Expected: "anana"
Run your code to see the results