Longest Palindromic Substring - Python Solution

1. Introduction

The "Longest Palindromic Substring" problem is a classic in string processing, focusing on finding the longest symmetrical sequence of characters within a string. This problem is commonly used to test the understanding of dynamic programming, string manipulation, and the concept of palindromes in computational algorithms.

Problem

Given a string s, the task is to return the longest palindromic substring in s. A palindrome is a string that reads the same forward and backward. The goal is to identify the longest contiguous sequence within s that satisfies this property.

2. Solution Steps

1. Create a helper function expandAroundCenter that takes parameters left and right indices and expands around the center to find the longest palindrome.

2. Initialize variables to track the start and length of the longest palindromic substring.

3. Iterate over the string, using each character and each pair of adjacent characters as potential centers.

4. Use expandAroundCenter to find palindromes and update the start and length if a longer palindrome is found.

5. Return the longest palindromic substring using the start and length variables.

3. Code Program

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

    start, end = 0, 0
    for i in range(len(s)):
        len1 = expandAroundCenter(i, i)
        len2 = expandAroundCenter(i, i + 1)
        maxLen = max(len1, len2)
        if maxLen > end - start:
            start = i - (maxLen - 1) // 2
            end = i + maxLen // 2

    return s[start:end + 1]

# Example Usage
print(longestPalindrome("babad"))  # Output: "bab" or "aba"
print(longestPalindrome("cbbd"))   # Output: "bb"

Output:

"bab"
"bb"

Explanation:

1. Center Expansion Technique: Expands around potential centers to find palindromes.

2. Handling Odd and Even Length: Considers both individual characters and pairs as centers for palindromes.

3. Dynamic Update: Updates the longest palindrome when a longer one is found.

4. Efficiency: The approach has O(n^2) time complexity and O(1) space complexity.

5. Flexibility: Can return any one of the longest palindromic substrings if multiple exist.

6. Practical Use Case: Useful in various scenarios, including text processing and sequence analysis.


Comments