Longest Palindromic Substring in Python

A palindromic substring is a sequence of characters within a string that reads the same backward as forward. For example, in the string "babad", the substrings "bab" and "aba" are both palindromic because they are the same when read from left to right and right to left.

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

1s = "babad"

Sample output

1output = "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:

1def longest_palindromic_substring(s):
2    if not s:
3        return ""
4
5    start, end = 0, 0
6
7    for i in range(len(s)):
8        len1 = expand_around_center(s, i, i)  # Odd length palindrome
9        len2 = expand_around_center(s, i, i + 1)  # Even length palindrome
10        max_len = max(len1, len2)
11        
12        if max_len > end - start:
13            start = i - (max_len - 1) // 2
14            end = i + max_len // 2
15    
16    return s[start:end + 1]
17
18def expand_around_center(s, left, right):
19    while left >= 0 and right < len(s) and s[left] == s[right]:
20        left -= 1
21        right += 1
22    return right - left - 1
23
24# Sample input
25s = "babad"
26# Calling the function and printing the result
27output = longest_palindromic_substring(s)
28print("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.