1. Introduction

The "Longest Palindromic Substring" problem is a classic challenge in string processing and dynamic programming. It involves finding the longest contiguous sequence of characters in a string that reads the same forwards and backwards. This problem is a great exercise for understanding string manipulation and algorithm optimization techniques.

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.

2. Solution Steps

1. Initialize variables to store the start and length of the longest palindrome found.

2. Iterate through each character in the string, treating it as the center of a potential palindrome.

3. Expand around the center to find the longest palindrome for both even and odd length palindromes.

4. Update the start and length variables if a longer palindrome is found.

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

3. Code Program

def longestPalindrome(s):
    if not s or len(s) < 1:
        return ""

    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"))
print(longestPalindrome("cbbd"))