Python - Longest Palindromic Substring

What is a Palindromic Substring?

A palindromic substring is a substring that reads the same forward and backward. The goal is to find the longest such substring in a given string.

Example 1

Input: "babad"

Output: "bab"  (or "aba" is also valid)

Example 2

Input: "cbbd"

Output: "bb"

Approach 1: Brute Force (O(N³))

Check all substrings and verify if they are palindromes.

def is_palindrome(s):

    return s == s[::-1]

def longest_palindrome(s):

    n = len(s)

    max_length = 0

    longest_substring = ""

    for i in range(n):

        for j in range(i, n):

            substring = s[i:j+1]

            if is_palindrome(substring) and len(substring) > max_length:

                max_length = len(substring)

                longest_substring = substring

    return longest_substring

# Example

print(longest_palindrome("babad"))  # Output: "bab" or "aba"

print(longest_palindrome("cbbd"))   # Output: "bb"