Longest Palindromic Substring
Given a string `s`, return the longest palindromic substring in `s`.
Examples
Constraints
1 <= s.length <= 1000s consist of only digits and English letters.
Expand Around Center
Approach
Instead of checking every possible substring (which takes O(n^3)), we can iterate through the string and treat each character (or each pair of characters) as the center of a potential palindrome. From the center, we expand outwards to the left and right as long as the characters match. We do this for both odd-length palindromes (single character center) and even-length palindromes (two-character center) at every index. We keep track of the longest palindrome found so far.
Complexity Analysis
Expanding around a center takes O(n) time, and we do this for 2n-1 centers (n characters and n-1 gaps between characters). Thus, the total time complexity is O(n^2). Space complexity is O(1) as we only keep track of indices and string lengths.
class Solution { public String longestPalindrome(String s) { if (s == null || s.length() < 1) return ""; int start = 0; int end = 0; for (int i = 0; i < s.length(); i++) { // Check for odd length palindromes (centered at i) int len1 = expandAroundCenter(s, i, i); // Check for even length palindromes (centered between i and i+1) int len2 = expandAroundCenter(s, i, i + 1); int len = Math.max(len1, len2); // If we found a longer palindrome, update start and end indices if (len > end - start) { // Calculation to find the start and end index from the center and length start = i - (len - 1) / 2; end = i + len / 2; } } return s.substring(start, end + 1); } private int expandAroundCenter(String s, int left, int right) { int L = left; int R = right; while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) { L--; R++; } // Return the length of the palindrome return R - L - 1; }}