Longest Palindromic Substring

Have you ever tried to find the longest palindromic substring in Python? A palindrome is a unique sequence of characters that reads the same forward and backward, such as "madam" or "level." Finding the longest palindrome in a string is a common interview question and a great way to sharpen your string manipulation skills in Python. Whether you're preparing for coding challenges or enhancing your Python knowledge, this problem will help you think critically and explore efficient algorithms. Want to learn step-by-step how to solve this and uncover the longest palindrome in Python strings? Let’s start with quick solution:

Steps to Solve Longest Palindromic Substring in Python

• Understand the Problem: The goal is to find the longest sequence in a Python string that reads the same backward and forward.
• Expand Around Each Character: Use a loop to treat each character as the center of a possible palindrome. Remember to check both odd-length and even-length palindromes.
• Compare and Track Length: As you expand around the center, keep track of the start and end indices of the longest palindrome substring found so far.
• Use a Helper Function: Create a function to expand around the center and return the length of the palindrome for each character or pair of characters.
• Handle Edge Cases: Test for edge cases such as strings with one character, all identical characters, or no palindromes.
• Optimize with Dynamic Programming: If dealing with very large strings, use a dynamic programming approach in Python to store previous results and reduce redundant calculations.
• Validate the Solution: Test your implementation with various palindromic string examples, like "babad" (output: "bab" or "aba") or "cbbd" (output: "bb").

Introduction

Finding the longest palindromic substring is a common problem in computer science and programming. It involves identifying the longest sequence within a string that forms a palindrome. This problem can help in various text processing applications and is a frequent question in coding interviews.

Problem statement

Given a string s, find the longest palindromic substring in s.

Sample input

1
s = "babad"

Sample output

1
output = "bab"  # or "aba", both are correct answers.

Real-life example

Consider developing a text editor with a feature that highlights the longest palindromic substring within a document. This feature can be useful for authors and researchers working with palindromic sequences in literature or data analysis.

Idea to solve

To find the longest palindromic substring, we can use dynamic programming or expand around center techniques. Here, we will discuss the expand around center approach, which is more intuitive and easier to implement.

Pseudo code

Here’s the pseudo code for solving the problem using the expand around center technique:

• Initialize start and end to mark the beginning and end of the longest palindromic substring found.
• Iterate through the string with an index i.
• For each character, consider it as the center of an odd-length palindrome and expand outward.
• Consider it as the center of an even-length palindrome and expand outward.
• Update the start and end if a longer palindrome is found.
• Return the substring from start to end + 1.

Full code

Here's the complete Python code to find the longest palindromic substring:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def longest_palindromic_substring(s):
    if not s:
        return ""

    start, end = 0, 0

    for i in range(len(s)):
        len1 = expand_around_center(s, i, i)  # Odd length palindrome
        len2 = expand_around_center(s, i, i + 1)  # Even length palindrome
        max_len = max(len1, len2)
        
        if max_len > end - start:
            start = i - (max_len - 1) // 2
            end = i + max_len // 2
    
    return s[start:end + 1]

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

# Sample input
s = "babad"
# Calling the function and printing the result
output = longest_palindromic_substring(s)
print("Longest Palindromic Substring:", output)

Explanation of the code

Initialization: We initialize start and end to mark the beginning and end of the longest palindromic substring found so far.

Iterate through the String: We use a for loop to iterate through the string. For each character, we consider it as the center of both odd-length and even-length palindromes.

Expand Around Center: The expand_around_center function expands outward from the given center and returns the length of the palindrome. We call this function twice for each character: once considering it as the center of an odd-length palindrome and once as the center of an even-length palindrome.

Update Longest Palindrome: We update start and end if a longer palindrome is found.

Return Result: After iterating through the string, we return the substring from start to end + 1.

Time complexity

The time complexity of this approach is O(n^2), where n is the length of the string. This is because we expand around each center, which takes linear time for each character. The space complexity is O(1) as we are using only a few extra variables.