Code Implementation

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if not s or len(s) == 1:
            return s

        start, end = 0, 0

        def expandAroundCenter(left: int, right: int) -> int:
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
            return right - left - 1

        for i in range(len(s)):
            len1 = expandAroundCenter(i, i)      # Odd length palindrome
            len2 = expandAroundCenter(i, i + 1)  # Even length palindrome
            max_len = max(len1, len2)
            if max_len > end - start:
                start = i - (max_len - 1) // 2
                end = i + max_len // 2

        return s[start:end+1]
      

class Solution {
public:
    string longestPalindrome(string s) {
        if (s.empty() || s.size() == 1) return s;
        int start = 0, end = 0;

        auto expandAroundCenter = [&](int left, int right) {
            while (left >= 0 && right < s.size() && s[left] == s[right]) {
                --left;
                ++right;
            }
            return right - left - 1;
        };

        for (int i = 0; i < s.size(); ++i) {
            int len1 = expandAroundCenter(i, i);       // Odd length
            int len2 = expandAroundCenter(i, i + 1);   // Even length
            int len = max(len1, len2);
            if (len > end - start) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        return s.substr(start, end - start + 1);
    }
};
      

class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 1) return s;
        int start = 0, end = 0;

        for (int i = 0; i < s.length(); i++) {
            int len1 = expandAroundCenter(s, i, i);
            int len2 = expandAroundCenter(s, i, i + 1);
            int len = Math.max(len1, len2);
            if (len > end - start) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        return s.substring(start, end + 1);
    }

    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;
    }
}
      

var longestPalindrome = function(s) {
    if (!s || s.length < 1) return s;
    let start = 0, end = 0;

    function expandAroundCenter(left, right) {
        while (left >= 0 && right < s.length && s[left] === s[right]) {
            left--;
            right++;
        }
        return right - left - 1;
    }

    for (let i = 0; i < s.length; i++) {
        let len1 = expandAroundCenter(i, i);
        let len2 = expandAroundCenter(i, i + 1);
        let len = Math.max(len1, len2);
        if (len > end - start) {
            start = i - Math.floor((len - 1) / 2);
            end = i + Math.floor(len / 2);
        }
    }
    return s.substring(start, end + 1);
};
      

Problem Description

Given a string s, you are asked to find the longest substring of s that is a palindrome. A palindrome is a string that reads the same backward as forward (e.g., "racecar", "abba").
Constraints:

• There is always at least one valid answer (the shortest palindrome is a single character).
• Return any one longest palindromic substring if there are multiple answers.

Thought Process

To solve this problem, the first idea that comes to mind is to check all possible substrings of s and determine if each is a palindrome, keeping track of the longest one found. However, this brute-force approach is inefficient, especially for long strings, because there are O(n²) substrings and each check can take up to O(n) time.

We need to optimize. One insight is that palindromes "expand" from their center. Every palindrome can be defined by its center and its length. For each character (and the gap between each pair of characters), we can try to expand outward as long as the substring remains a palindrome. This reduces unnecessary checks and improves performance.

This leads us to the "expand around center" approach, which is both intuitive and efficient for this problem.

Solution Approach

The optimized solution uses the "expand around center" technique. Here's how it works step by step:

1. Consider each character (and gap) as a center:
   • There are 2n-1 possible centers in a string of length n (n characters and n-1 gaps between characters).
   • For each center, try to expand outwards as long as the characters on both sides are equal.
2. Expand around the center:
   • For index i, expand for both odd-length palindromes (centered at i) and even-length palindromes (centered between i and i+1).
   • Keep expanding as long as the characters match and the indices are within bounds.
3. Track the longest palindrome:
   • For each expansion, if a longer palindrome is found, update the start and end indices.
   • At the end, return the substring from start to end (inclusive).

This approach ensures we check all possible palindromic substrings efficiently, without redundant checks.

Example Walkthrough

Let's walk through the process with the input s = "babad":

1. i = 0 ("b"):
   • Odd-length: expand from center 0, palindrome is "b".
   • Even-length: expand from centers 0 and 1, not a palindrome.
   • Longest so far: "b" (indices 0-0)
2. i = 1 ("a"):
   • Odd-length: expand from center 1, palindrome is "aba".
   • Even-length: expand from centers 1 and 2, not a palindrome.
   • Longest so far: "bab" (indices 0-2)
3. i = 2 ("b"):
   • Odd-length: expand from center 2, palindrome is "bab".
   • Even-length: expand from centers 2 and 3, not a palindrome.
   • Longest so far: "bab" (indices 0-2)
4. i = 3 ("a"):
   • Odd-length: expand from center 3, palindrome is "ada".
   • Even-length: expand from centers 3 and 4, not a palindrome.
   • Longest so far: "aba" or "bab" (indices 1-3)
5. i = 4 ("d"):
   • Odd-length: expand from center 4, palindrome is "d".
   • Even-length: expand from centers 4 and 5, not a palindrome.
   • Longest so far: "aba" or "bab"

The function can return either "bab" or "aba" as both are valid longest palindromic substrings.

Time and Space Complexity

• Brute-force approach:
  • Time Complexity: O(n³) — O(n²) substrings and O(n) for each palindrome check.
  • Space Complexity: O(1) if done in-place.
• Expand Around Center approach (this solution):
  • Time Complexity: O(n²) — For each center (2n-1 total), each expansion takes O(n) in the worst case.
  • Space Complexity: O(1) — Only a few pointers/variables are used, no extra arrays.

Summary

The "Longest Palindromic Substring" problem can be solved efficiently using the expand around center technique. This approach leverages the symmetrical property of palindromes, checking all possible centers and expanding outwards to find the maximum-length palindrome. It is both intuitive and efficient, with a manageable O(n²) time complexity and O(1) space usage. The key insight is that all palindromes can be defined by their centers, avoiding redundant checks and unnecessary computations.