LeetCode Problem – 5 (Longest Palindromic Substring)

Longest Palindromic Substring

Today, we’re dissecting a popular problem from LeetCode: finding the longest palindromic substring in a given string. This puzzle is not just a common interview question, but also a great way to enhance your understanding of strings and algorithms.

What Is a Palindromic Substring?

Before we jump into solving, let’s clear up what we’re searching for. A palindrome is a sequence of characters that reads the same backward as forward, like “radar” or “level”. A palindromic substring, then, is a section of a larger string that maintains this characteristic.

Problem :

Given a string s, return the longest 

palindromic

substring in s.

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 consist of only digits and English letters.

Solution :

class Solution:
    def longestPalindrome(self, s: str) -> str:
        long_str = ""
        n = len(s)
        if n <= 1:
            return s
        for i in range(n):
            for j in range(i + len(long_str), n + 1):
                st = s[i:j]
                if st == st[::-1]:
                    if len(st) > len(long_str):
                        long_str = st
                    if len(long_str) == n:
                        break
        return long_str

Breaking Down the Code

• We start with a method longestPalindrome within the Solution class.
• An empty string long_str is initialized to store the longest palindrome.
• If the input string s is 1 character or less, it’s a palindrome by default.
• We iterate over each character, checking every possible substring from that point.
• If a substring is a palindrome and longer than our current long_str, we update it.
• We end the search if we find a palindrome as long as the entire string.

Time Complexity

The time complexity here is O(n^3) – for each substring (O(n^2) of them), we check if it’s a palindrome (O(n)). While this is fine for shorter strings, for more extended strings, more efficient algorithms are available.