Question 5

Longest Palindromic Substring

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

Approach: Expand Around Center

To find the longest palindromic substring efficiently, we can use the "Expand Around Center" technique. A palindrome mirrors around its center, so for each character in the string, we can consider it as the center and try to expand outwards in both directions to find the longest palindrome. We need to check both odd-length and even-length palindromes by treating each character and each pair of characters as potential centers.

Steps

1. Initialize Variables:

   • Initialize start and end pointers to keep track of the starting and ending indices of the longest palindromic substring found.

2. Expand Around Centers:

   • For each character at position i in s, expand around i for both odd-length and even-length palindromes.
   • Calculate the length of the palindrome for both cases:
     • len1: Palindrome with a single character center (odd length).
     • len2: Palindrome with two-character center (even length).
   • Use the maximum length of these two palindromes to determine the current longest palindrome. If this length is greater than the previous longest, update start and end indices accordingly.

3. Extract the Longest Palindrome:

   • After checking all centers, s.substring(start, end + 1) will be the longest palindromic substring.

4. Time Complexity:

   • O(n²), where n is the length of the string s. For each character, we consider it as a potential center of a palindrome. There are:
     • n possible centers for palindromes of odd length (each individual character),
     • n - 1 possible centers for palindromes of even length (each pair of consecutive characters).

Code

Here's the Java implementation:

public class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 1) return "";
        
        int start = 0, end = 0;
        
        for (int i = 0; i < s.length(); i++) {
            // Check for odd-length palindromes
            int len1 = expandAroundCenter(s, i, i);
            // Check for even-length palindromes
            int len2 = expandAroundCenter(s, i, i + 1);
            
            // Get the maximum length from both cases
            int len = Math.max(len1, len2);
            
            // Update start and end pointers if a longer palindrome is found
            if (len > end - start) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        
        // Return the longest palindromic substring
        return s.substring(start, end + 1);
    }
    
    // Helper function to expand around the center
    private int expandAroundCenter(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return right - left - 1;
    }
}