52. Longest Palindromic Substring

Given a string s, find its longest substring that is a palindrome. If there are multiple of the same maximum length, print the one that starts earliest.

Input: A single line containing the string s. Output: Print the longest palindromic substring of s (the earliest-starting one if there's a tie in length).

1 <= |s| <= 2000

Remembering to check BOTH odd-length centers (a single character) and even-length centers (the gap between two characters) is essential - forgetting even-length centers would miss palindromes like 'abba' entirely.

Find the longest contiguous stretch of a string that reads the same forwards and backwards. Brute force: Check every possible substring directly, verifying if each one is a palindrome - this costs O(n³) (O(n²) substrings, each taking O(n) to verify), too slow for longer strings. Optimised: Expanding outward from each of the 2n-1 possible centers (rather than checking every substring independently) directly finds the largest palindrome AT that center in time proportional to its own length - across all centers this costs O(n²) total, a solid improvement over the cubic brute force, and simpler to implement correctly than the more advanced O(n) Manacher's algorithm.

Transform the string by inserting separator characters between every character (and at both ends) so odd and even-length palindromes are handled uniformly, then compute, for every position, the radius of the longest palindrome centered there - reusing previously computed radii of positions inside the current longest-known palindrome's mirror range to avoid re-expanding from scratch wherever possible, only falling back to direct character comparison at the boundary. This exploits the symmetry of palindromes themselves to guarantee every character is involved in only a constant amount of comparison work overall, achieving linear time, an asymptotic improvement over both the cubic brute force and the quadratic DP table. Time: O(n) Space: O(n)

Build a 2D boolean table isPalindrome[i][j] indicating whether the substring from i to j is a palindrome, filled in order of increasing substring length: a length-1 substring is always a palindrome, a length-2 substring is a palindrome iff its two characters match, and a longer substring s[i..j] is a palindrome iff s[i] == s[j] and isPalindrome[i+1][j-1] is already true. Reusing these previously computed shorter-substring results avoids re-verifying overlapping substrings from scratch, cutting the verification cost from linear-per-substring down to constant-per-substring, at the cost of storing the whole table. Time: O(n^2) Space: O(n^2)

Generate every possible substring of s (defined by its start and end indices), and for each one check whether it reads the same forwards and backwards by comparing characters from both ends inward, keeping track of the longest one found so far (preferring the earliest start on ties). This checks every candidate directly and is unquestionably correct, but both generating O(n^2) substrings and verifying each in O(n) time makes it cubic overall. Time: O(n^3) Space: O(1)

1. For every possible CENTER point in the string (both single-character centers, for odd-length palindromes, and between-character centers, for even-length ones), expand outward in both directions as long as the characters keep matching. 2. Track the longest palindrome found this way across every possible center. 3. If multiple palindromes tie for the longest length, keep the one that started earliest.

Time: O(n²) - expanding from each of the 2n-1 centers costs up to O(n) in the worst case. Space: O(1) extra space beyond tracking the best palindrome's start and length found so far.

Test with |s|=1 (trivially the whole string), a string with no repeated adjacent/mirrored characters (answer length 1), an all-identical-character string (whole string is the answer), and |s|=2000 to confirm O(n^2) performance.

Be ready to mention Manacher's algorithm as the theoretically optimal O(n) approach for this exact problem, even while defaulting to the simpler, more commonly expected 'expand around center' O(n²) solution unless specifically asked to push further.