5. Longest Palindromic Substring
Given a string s, return the longest palindromic substring of s.
A palindrome reads the same forwards and backwards (for example racecar or bb). A substring is a contiguous run of characters taken from s.
If several substrings share the same maximal length, return the one that starts at the smallest index (the leftmost such substring). Because a single character is always a palindrome, an answer always exists.
Example 1:
Input: s = "babad"
Output: "bab"
Explanation: Both "bab" and "aba" are palindromes of length 3, but "bab" begins at index 0 while "aba" begins at index 1, so the leftmost one wins.
Example 2:
Input: s = "cbbd"
Output: "bb"
Explanation: The only length-2 palindrome is "bb", every other palindromic substring is a single character.
Constraints:
- 1 ≤ s.length ≤ 1000
- `s` consists only of digits and English letters.
Hints:
A palindrome mirrors around its center. A string of length n has 2n - 1 possible centers: n on a character (odd length) and n - 1 between two characters (even length).
From each center, expand outward while the two ends match, and track the longest span you have seen. Use a strict `>` comparison when updating the best so that on a length tie you keep the earliest (leftmost) center.
Alternatively, fill a boolean table dp[i][j] = 'is s[i..j] a palindrome?' by increasing length: s[i..j] is a palindrome when s[i] == s[j] and the inside s[i+1..j-1] already is.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: s = "babad"
Expected output: "bab"