Longest Palindromic Substring Leetcode Problem 5 [Python Solution]

Welcome to another exciting problem-solving session!

In this blog post, we’re going to tackle the Longest Palindromic Substring problem from LeetCode.

You can find the original question here.

Problem Overview

The problem statement is as follows: Given a string s, we need to find and return the longest palindromic substring within it.

A palindromic substring is a string that reads the same backward as forwards.

For instance, in the string “babad,” both “bab” and “aba” are valid palindromic substrings.

Let’s dive deeper into the problem, explore some examples, understand the constraints, and discuss the best approach to solve it.

Example 1:

Input: s = “babad”
Output: “bab”
Explanation: “aba” is also a valid answer.

Example 2:

Input: s = “cbbd”
Output: “bb”

Constraints:

• 1 <= s.length <= 1000
• s consists of only digits and English letters.

Understanding Palindromic Constraints

To solve this problem effectively, we need to grasp the concept of palindromes and how we can identify them within a given string.

A palindromic substring is a sequence of characters that reads the same forwards and backward.

For example, “racecar” is a palindrome because it remains unchanged even when reversed.

In our problem, we want to find the longest such substring within a given string s.

Now, before we jump into the solution, let’s consider the constraints and an edge case that’s important to keep in mind.

Edge Cases a Valid Solution Must Consider

One of the critical edge cases to consider is when the longest palindromic substring has an even length.

Let’s take an example to illustrate this.

In the string “babad,” the longest palindromic substring is “bab,” which has an odd length.

However, in the string “cbbd,” the longest palindromic substring is “bb,” which has an even length.

We need to ensure our solution can handle both odd and even-length palindromes.

Longest Palindromic Substring LeetCode Problem Solution

1. Bruteforce Approach

Let’s start by discussing the most straightforward, but less efficient, approach to solving this problem.

The brute-force method would be to check every possible substring in the given string and determine if it is a palindrome.

This approach involves checking every combination, which results in a time complexity of O(n^3), where ‘n’ is the length of the input string s.

Here’s a high-level overview of the brute-force solution:

def longestPalindrome(s: str) -> str:
result = ""

for i in range(len(s)):
    for l, r in ((i, i), (i, i + 1)): # Odd and even lengths
        while l >= 0 and r < len(s) and s[l] == s[r]:
            if (r - l + 1) > len(result):
                result = s[l:r + 1]
            l -= 1
            r += 1

return result

In this approach, we iterate through the string, considering each character as the potential center of a palindrome.

We then expand outwards in both directions, checking if the substring is a palindrome.

We keep track of the longest palindrome we’ve encountered so far and return it at the end.

While this solution works, it’s not the most efficient way to solve the problem.

To optimize it, we’ll explore a more efficient approach.

2. An Efficient Approach

To optimize our solution, we’ll use a different strategy.

Instead of checking all substrings to see if they’re palindromes, we’ll leverage the characteristics of palindromes to reduce our search space.

In the efficient approach, we’ll follow these steps:

1. Initialize an empty string `result` to store the longest palindromic substring found.
2. Initialize a variable `max_length` to keep track of the maximum palindrome length.
3. Iterate through the input string `s`, treating each character as a potential center of a palindrome.
– For odd-length palindromes, we expand around the center character.
– For even-length palindromes, we expand around the center characters (two characters).
4. While expanding from the center, we compare characters on the left and right sides to determine if the substring is a palindrome.
5. If we find a longer palindrome, we update the `result` and `max_length`.
6. Return the longest palindromic substring found.

Here’s the Python code for this efficient approach:

View on GitHub ➹
def longestPalindrome(s: str) -> str:
if len(s) < 2:
return s

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

result = ""
max_length = 0

for i in range(len(s)):
    # Odd length palindrome
    palindrome1 = expand_around_center(i, i)
    if len(palindrome1) > max_length:
        result = palindrome1
        max_length = len(palindrome1)

    # Even length palindrome
    palindrome2 = expand_around_center(i, i + 1)
    if len(palindrome2) > max_length:
        result = palindrome2
        max_length = len(palindrome2)

return result