LeetCode Solution: 5. Longest Palindromic Substring

5. Longest Palindromic Substring: Unraveling the Palindromic Puzzle 🧩

Hey fellow coders! 👋 Today, we're diving into a LeetCode classic that often stumps beginners but reveals a really elegant pattern once you spot it: the Longest Palindromic Substring problem.

Don't let the fancy name scare you! We'll break it down piece by piece, find an intuitive way to tackle it, and emerge victorious with a neat, efficient solution. Ready? Let's go!

📜 Problem Explanation

The problem asks us to find the longest palindromic substring within a given string s.

"Whoa, hold on!" you might say. "What's a palindrome? And what's a substring?" Great questions!

• Palindrome: A string that reads the same forwards and backward. Think words like "madam", "racecar", or even single letters like "a".
• Substring: A contiguous sequence of characters within a string. For "babad", "bab", "aba", "bad", "a" are all substrings. "bba" is not a substring because the 'b's aren't contiguous in that order.

So, our mission is to scan through the given string s, find all possible substrings that are also palindromes, and then return the longest one among them.

Let's look at the examples:

• Example 1: s = "babad"
  • Possible palindromic substrings: "b", "a", "b", "a", "d", "bab", "aba".
  • The longest ones are "bab" and "aba". Either is a valid answer.
• Example 2: s = "cbbd"
  • Possible palindromic substrings: "c", "b", "b", "d", "bb".
  • The longest is "bb".

Constraints:

• The string s will have between 1 and 1000 characters.
• It will only contain digits and English letters. No weird symbols to worry about!

🤔 Intuition: Don't Brute Force, Explore From the Middle!

A common first thought for many string problems is: "Let's check every possible substring!"

If you have a string of length N:

1. There are N * (N + 1) / 2 possible substrings (e.g., for "abc", "a", "b", "c", "ab", "bc", "abc").
2. For each substring, checking if it's a palindrome takes O(length_of_substring) time.
3. This quickly leads to an O(N^3) solution, which for N=1000 is 1000^3 = 1,000,000,000 operations – way too slow! 🐌

We need something smarter.

What makes a palindrome special? It's symmetrical around its center!

Consider "racecar":
r a c e c a r
The e is the center. Everything expands outwards equally.

Consider "abba":
a b b a
The "center" is between the two bs.

This gives us a huge hint! Instead of picking two ends and checking inwards, what if we pick a center and expand outwards?

Every palindrome has a center:

• Odd-length palindromes: A single character is the center (e.g., 'a' in "bab", 'e' in "racecar").
• Even-length palindromes: The "center" is the space between two identical characters (e.g., the space between the two 'b's in "bb", or "abba").

This means we can iterate through every possible "center" in our string and try to expand outwards to find the longest palindrome centered there. Since there are N characters and N-1 spaces between characters, there are roughly 2N - 1 potential centers.

🚀 Approach: Expand Around Center

Our intuition leads us to a solid plan:

1. We'll maintain variables start and max_len to keep track of the beginning index and length of the longest palindrome we've found so far. Initialize start = 0 and max_len = 1 (a single character is always a palindrome).
2. We'll iterate through each character in the string s using an index i. For each i, we consider it as a potential center for a palindrome.
3. Since palindromes can be odd or even length, we'll need to check two types of expansions for each i:
   • Odd length: i itself is the center. We'll try to expand outwards from left = i, right = i.
   • Even length: The space after i is the center. We'll try to expand outwards from left = i, right = i + 1.
4. To avoid repeating code, we'll create a helper function, let's call it expandAroundCenter(s, left, right). This function will take the string s and two pointers, left and right, and expand them outwards as long as:
   • left is not less than 0 (we're within string bounds).
   • right is not greater than or equal to len(s) (we're within string bounds).
   • s[left] is equal to s[right] (the characters match, so it's still a palindrome).
   • Once these conditions are no longer met, the function returns the length of the palindrome found (which is right - left - 1).
5. In our main loop, after calling expandAroundCenter for both odd and even cases, we'll compare the lengths of the palindromes found. If either is longer than our current max_len, we update max_len and calculate the new start index. The start index will be i - (current_palindrome_length - 1) // 2. (This formula looks tricky, but it simply finds the leftmost character of the new longest palindrome given its length and its "center" i).
6. After checking all possible centers, we return the substring s[start : start + max_len].

Let's trace s = "babad":

• Initialize start = 0, max_len = 1 (our initial "b")
• i = 0 (char 'b')
  • expandAroundCenter(s, 0, 0) -> returns length 1 ("b")
  • expandAroundCenter(s, 0, 1) -> 'b' != 'a', returns length 0
• i = 1 (char 'a')
  • expandAroundCenter(s, 1, 1) -> returns length 1 ("a")
  • expandAroundCenter(s, 1, 2) -> 'a' == 'b' NO, returns length 0
  • expandAroundCenter(s, 0, 2) for center 'a': s[0]=='b', s[2]=='b'. left becomes -1, right becomes 3. Palindrome is "bab", length 3.
    • max_len = 3, start = 1 - (3-1)//2 = 1 - 1 = 0. Current best: "bab".
• i = 2 (char 'b')
  • expandAroundCenter(s, 2, 2) -> returns length 1 ("b")
  • expandAroundCenter(s, 2, 3) -> 'b' != 'a', returns length 0
  • expandAroundCenter(s, 1, 3) for center 'b': s[1]=='a', s[3]=='a'. left becomes 0, right becomes 4. Palindrome is "aba", length 3.
    • Length is 3, same as current max_len. We don't need to update start and max_len if it's not strictly greater, but it's fine if we do (it would become "aba"). Let's say it updates to "aba".
• ... and so on.

Finally, we return s[start : start + max_len].

💻 Code

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

        # Helper function to expand around a center
        # It takes the string s, and the left and right pointers
        # It expands outwards as long as characters match and stay within bounds
        # Returns the length of the palindrome found
        def expandAroundCenter(left: int, right: int) -> int:
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
            # After the loop, left and right are one step *past* the palindrome
            # So, the length is (right - 1) - (left + 1) + 1 = right - left - 1
            return right - left - 1

        start_index = 0  # Stores the starting index of the longest palindrome
        max_length = 0   # Stores the maximum length found so far

        # Loop through each character to consider it as a center
        for i in range(len(s)):
            # Case 1: Odd length palindrome (e.g., "aba", "racecar")
            # The current character s[i] is the center
            len1 = expandAroundCenter(i, i)

            # Case 2: Even length palindrome (e.g., "abba", "bb")
            # The center is between s[i] and s[i+1]
            len2 = expandAroundCenter(i, i + 1)

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

            # If this palindrome is longer than our current max_length
            if current_max_len > max_length:
                max_length = current_max_len
                # Calculate the new starting index for this longest palindrome
                # For an odd length palindrome, start = i - (length - 1) / 2
                # For an even length palindrome, start = i - (length / 2 - 1)
                # Both can be generalized as: i - (length - 1) // 2
                start_index = i - (max_length - 1) // 2

        # Return the substring from start_index with max_length
        return s[start_index : start_index + max_length]

⏱️ Time & Space Complexity Analysis

Let's break down how efficient our solution is:

• Time Complexity: O(N^2)

  • The main for loop iterates N times (once for each character in s).
  • Inside the loop, we call expandAroundCenter twice.
  • The expandAroundCenter function, in the worst case (e.g., s = "aaaaa"), might expand all the way to the boundaries of the string. This takes O(N) time.
  • Therefore, the total time complexity is N * O(N) = O(N^2).
  • Given N <= 1000, N^2 is 1,000,000, which is perfectly acceptable within typical time limits (usually around 10^8 operations per second).

• Space Complexity: O(1)

  • We are only using a few constant variables (start_index, max_length, i, len1, len2, left, right). We are not storing any data structures that grow with the input size N.
  • The slicing s[start_index : start_index + max_length] creates a new string, but this is part of the output, not auxiliary space used by the algorithm itself.

🌟 Key Takeaways

1. Don't Jump to Brute Force: Always consider the constraints and think about whether a naive O(N^3) or O(N^2) approach will pass. Often, there's a more elegant pattern waiting to be discovered!
2. Palindromes and Symmetry: The core idea for many palindrome problems revolves around their symmetrical nature. Thinking about "centers" is a powerful paradigm.
3. Odd vs. Even Length: Remember that palindromes can have either odd or even lengths, and your solution needs to account for both types of "centers."
4. Helper Functions: Breaking down complex logic into smaller, reusable helper functions (like expandAroundCenter) makes your code cleaner, more readable, and easier to debug.
5. Smallest Palindrome is 1: Don't forget that a single character is always a palindrome, which can be useful for initializing max_length.

This problem is a fantastic introduction to dynamic programming and string algorithms, and mastering the "expand around center" technique will serve you well in many other coding challenges!

Happy coding! ✨

---

Submission Details

• Author Account: aryan-subudhi
• Publishing Time: 2026-05-25 23:24:13