Longest Palindromic Substring Problem Statement

Given a string s, return the longest palindromic substring in s.

Example:

Input: s = "babad" Output: "bab" (or "aba")

Note: You may assume that the input string is non-empty.

Question

Given a string s, return the longest palindromic substring in s.

Input: s = "babad" Output: "bab" (or "aba")

Note: You may assume that the input string is non-empty.

Accepted Answer

Find the longest substring in a given string that reads the same forwards and backwards.

Use dynamic programming to build a table that tracks palindromic substrings.
Expand around potential centers (each character and between characters) to find palindromes.
Example: In 'babad', 'bab' and 'aba' are both valid longest palindromic substrings.
Example: In 'cbbd', 'bb' is the longest palindromic substring.

Interview Questions from Popular Companies