You get a string. Return its longest substring that is a palindrome. A palindrome reads the same forwards and backwards.
DSA Animator › DSA Revision › Strings › Longest Palindromic Substring
Remember: expand around 2 n minus 1 centers, both odd and even. Keep only the longest expansion. The video solves Longest Palindromic Substring (LeetCode 5, Medium) with the Expand Around Center pattern from the Strings topic, and you can replay every step in the interactive Longest Palindromic Substring animation.
You get a string. Return its longest substring that is a palindrome. A palindrome reads the same forwards and backwards.
In b a b a d, b a b is a palindrome. a b a is too, and both have length 3, so either answer is accepted.
Building every substring and checking whether it is a palindrome is O of n cubed. That is far too slow.
Every palindrome has a center. Treat each index as a center, and expand to both sides while the two ends match. But note that a palindrome like b b has its center between two characters. So expand twice at every index: once from a single character, and once from the gap after it.
Index 0 is b, with nothing to its left, so the length is 1. Index 1: treat a as the center. Both sides are b, which match, so b a b has length 3, a new best. Expand again, and the string ends on the left, so stop. Index 2: center on b, both sides are a, so a b a also has length 3, but that is not longer. Further out, b and d differ, so stop. The two-character centers, like b a or a b, never match here. Indexes 3 and 4 find nothing longer either. The answer is b a b.
In code, at every index call expand twice: once from i and i, and once from i and i plus 1. Expand moves left and right outward while the characters match, and returns the length. When a longer length appears, update the start and end. Time is O of n squared, and space is O of 1.
Remember: expand around 2 n minus 1 centers, both odd and even. Keep only the longest expansion.