LeetCode Solution: 5. Longest Palindromic Substring

#leetcode #dsa #programming #tutorial

Longest Palindromic Substring: A Core String Algorithm Explained

Welcome to another deep dive into a classic LeetCode problem! Today, we're tackling Problem 5: Longest Palindromic Substring. This problem is a fantastic way to sharpen your string manipulation and algorithmic thinking skills.

Problem Explanation

Given a string s, our goal is to find and return the longest substring within s that is a palindrome.

What's a palindrome? It's a sequence of characters that reads the same forwards and backward (e.g., "madam", "racecar", "level").
What's a substring? It's a contiguous sequence of characters within a string (e.g., for "apple", "app" is a substring, but "ale" is not).

Let's look at the examples:

Example 1:
- Input: s = "babad"
- Output: "bab"
- Explanation: "aba" is also a valid answer of the same length.
Example 2:
- Input: s = "cbbd"
- Output: "bb"

The string s will contain only digits and English letters, and its length will be between 1 and 1000 characters.

Intuition

The core idea behind finding palindromes is that they expand symmetrically from a center point. Think about "racecar" – the 'e' is the center, and 'c' expands to 'r'. Or "abba" – the center is between the two 'b's, and 'a' expands to 'a'.

This insight simplifies our search: instead of checking every single substring for palindromic properties (which is O(N^3) or O(N^2) with an O(N) check), we can iterate through every possible "center" and try to expand outwards.

There are two types of centers we need to consider:

Single character center: For palindromes with an odd length (e.g., "b*ab", "ra*cecar"). Here, s[i] itself is the center.
Two character center: For palindromes with an even length (e.g., "bb", "a*bb*a"). Here, s[i] and s[i+1] form the center.

Approach

We'll use an "Expand Around Center" approach:

Initialize: Keep track of the start and end indices of the longest palindrome found so far. Initialize them to 0, 0 (assuming a single character is the shortest possible palindrome).
Iterate Through Centers: Loop through each character in the string using an index i. Each i will serve as a potential center.
Expand for Odd Length Palindromes: Call a helper function expand_around_center(s, i, i). This tries to expand a palindrome assuming s[i] is its sole center.
Expand for Even Length Palindromes: Call the helper function expand_around_center(s, i, i + 1). This tries to expand a palindrome assuming s[i] and s[i+1] are its two central characters.
Helper Function expand_around_center(s, left, right):
- This function takes the string s and two indices, left and right.
- It expands outwards: left moves to the left (left-1) and right moves to the right (right+1).
- This expansion continues as long as left is within bounds (>= 0), right is within bounds (< len(s)), and the characters at s[left] and s[right] are equal.
- Once the loop terminates (either due to bounds or mismatch), the length of the palindrome found is right - left - 1.
Update Longest Palindrome: After getting len1 (odd center) and len2 (even center), determine max_len = max(len1, len2). If max_len is greater than the length of our current longest palindrome (end - start + 1), then update start and end.
- To calculate the new start and end from i and max_len:
  - start = i - (max_len - 1) // 2
  - end = i + max_len // 2
Return Result: After iterating through all possible centers, return the substring s[start : end + 1].

Code

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if not s:
            return ""

        start = 0
        end = 0

        # Helper function to expand around a given center
        def expand_around_center(s: str, left: int, right: int) -> int:
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
            # When the loop finishes, left and right are one step beyond the palindrome boundaries.
            # So, the length is (right - 1) - (left + 1) + 1 = right - left - 1
            return right - left - 1

        # Iterate through each character, treating it as a potential center
        for i in range(len(s)):
            # Case 1: Odd length palindrome (center is s[i])
            len1 = expand_around_center(s, i, i)

            # Case 2: Even length palindrome (center is s[i] and s[i+1])
            len2 = expand_around_center(s, i, i + 1)

            # Get the maximum length found from these two expansions
            max_len = max(len1, len2)

            # If this palindrome is longer than our current longest
            if max_len > end - start + 1:
                # Calculate the new start and end indices
                # For an odd length palindrome centered at i: start = i - (length-1)/2, end = i + (length-1)/2
                # For an even length palindrome centered between i and i+1: start = i - (length/2 - 1), end = i + length/2
                # The combined formula works for both:
                start = i - (max_len - 1) // 2
                end = i + max_len // 2

        # Return the longest palindromic substring
        return s[start : end + 1]

Time & Space Complexity Analysis

Time Complexity: O(N^2)
- The main loop iterates N times, where N is the length of the string s.
- Inside the loop, expand_around_center is called twice. In the worst case, expand_around_center might traverse the entire string (e.g., for "aaaa...a").
- Thus, each call to expand_around_center takes O(N) time.
- Overall complexity: N * O(N) = O(N^2).
Space Complexity: O(1)
- We are only using a few variables (start, end, i, len1, len2, max_len, left, right) to store indices and lengths.
- The space used does not grow with the input string size.

Key Takeaways

Palindromes and Symmetry: The inherent symmetry of palindromes is key to efficient algorithms.
Expand Around Center: This is a powerful technique for palindrome problems, allowing us to find palindromes by growing them from every possible middle point.
Handling Odd and Even Lengths: Remember to consider both types of palindromes (odd-length with a single character center, and even-length with a two-character center).

This "Expand Around Center" approach is generally simpler to implement than dynamic programming solutions for this problem, while achieving the same O(N^2) time complexity.

Author Account: p1Hzd8mRM8
Time Published: 2026-05-17 00:13:54