Finding the Longest Palindromic Substring in Python
A palindromic substring is a sequence of characters that reads the same backward as forward. To determine the longest palindromic substring in a given string, one effective approach is to use the "expand around center" technique, which has a time complexity of O(n^2) and a space complexity of O(1).
Below is a Python function that implements this technique:
def longest_palindromic_substring(s: str) -> str:
if not s:
return ""
start, end = 0, 0
for i in range(len(s)):
len1 = expand_around_center(s, i, i) # Odd length palindromes
len2 = expand_around_center(s, i, i + 1) # Even length palindromes
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: str, left: int, right: int) -> int:
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
return right - left - 1
How It Works
1. Function Definition: The function longest_palindromic_substring takes a string s as input and initializes two variables, start and end, to keep track of the current longest palindromic substring's starting and ending indices.
2. Iterating Through the String: The function iterates over each character in the string, treating each character (and the gap between characters) as a potential center for palindromes.
3. Expanding Around Centers: For each character:
- The function checks for odd-length palindromes by calling expand_around_center(s, i, i).
- It checks for even-length palindromes by calling expand_around_center(s, i, i + 1).
4. Updating Indices: If a longer palindromic substring is found (i.e., max_len), the start and end indices are updated.
5. Returning the Result: The substring is extracted using the calculated start and end indices and returned as the result.
Example Usage
Here’s how to use the function to find the longest palindromic substring:
input_string = "babad"
result = longest_palindromic_substring(input_string)
print(f"The longest palindromic substring of '{input_string}' is '{result}'")
Output
For the above example, possible outputs include "bab" or "aba" since both are valid palindromic substrings of the same maximum length.
This approach provides a straightforward solution for finding the longest palindromic substring efficiently.