Introduction to the Longest Palindromic Substring Problem
The Longest Palindromic Substring is one of the most classic problems in computer science and a frequent guest in coding interviews at companies like Amazon, Microsoft, and Google. A palindrome is a string that reads the same forward and backward, such as "racecar" or "madam". The challenge is to find the longest contiguous substring within a given string that satisfies this property.
While the problem statement is deceptively simple, the variety of approaches — ranging from brute force to dynamic programming to advanced linear-time algorithms — makes it an excellent vehicle for learning algorithm design, complexity analysis, and Python-specific optimization techniques.
What Is a Palindromic Substring?
Before diving into solutions, let's clarify the terminology. Given a string s, a substring is a contiguous sequence of characters within s. A palindromic substring is one where the sequence of characters is identical when reversed. For example, in the string "babad", both "bab" and "aba" are valid palindromic substrings, and either is a valid answer for the longest one.
Note the distinction between a substring and a subsequence: a subsequence does not need to be contiguous, but a substring does. This distinction matters because it constrains the kinds of algorithms we can apply.
Why This Problem Matters
- Interview relevance: It tests your ability to reason about string manipulation, edge cases, and time/space tradeoffs.
- Algorithmic depth: It introduces concepts like dynamic programming, expand-around-center, and Manacher's algorithm.
- Real-world applications: Palindromic patterns appear in DNA sequence analysis, text processing, and data compression.
- Python fluency: It provides an opportunity to leverage Python's slicing, string methods, and built-in functions effectively.
Approach 1: Brute Force
The most intuitive approach is to generate every possible substring and check whether each one is a palindrome. While this is easy to understand, it is inefficient for large inputs.
Implementation
def is_palindrome(s: str) -> bool:
return s == s[::-1]
def longest_palindrome_brute(s: str) -> str:
n = len(s)
longest = ""
for i in range(n):
for j in range(i, n):
substring = s[i:j + 1]
if is_palindrome(substring) and len(substring) > len(longest):
longest = substring
return longest
# Example usage
print(longest_palindrome_brute("babad")) # Output: "bab" or "aba"
print(longest_palindrome_brute("cbbd")) # Output: "bb"
Complexity Analysis
There are O(n²) substrings, and checking each one takes O(n) time, resulting in an overall time complexity of O(n³). The space complexity is O(n) for storing the longest substring. This approach is acceptable only for very short strings (n ≤ 20) and is impractical for real-world use.
Approach 2: Expand Around Center
A more efficient approach leverages the fact that a palindrome mirrors around its center. A center can be a single character (for odd-length palindromes like "aba") or a pair of characters (for even-length palindromes like "abba"). By expanding outward from each possible center, we can find the longest palindrome in O(n²) time and O(1) space.
Implementation
def expand_around_center(s: str, left: int, right: int) -> str:
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
# Return the palindrome substring (exclusive bounds adjusted)
return s[left + 1:right]
def longest_palindrome_expand(s: str) -> str:
if not s:
return ""
longest = ""
for i in range(len(s)):
# Odd-length palindrome (single character center)
odd_palindrome = expand_around_center(s, i, i)
if len(odd_palindrome) > len(longest):
longest = odd_palindrome
# Even-length palindrome (two character center)
even_palindrome = expand_around_center(s, i, i + 1)
if len(even_palindrome) > len(longest):
longest = even_palindrome
return longest
# Example usage
print(longest_palindrome_expand("babad")) # Output: "bab" or "aba"
print(longest_palindrome_expand("cbbd")) # Output: "bb"
print(longest_palindrome_expand("a")) # Output: "a"
print(longest_palindrome_expand("ac")) # Output: "a" or "c"
Complexity Analysis
There are 2n - 1 possible centers (n single-character centers and n - 1 two-character centers). Expanding around each center takes O(n) time in the worst case, giving a total time complexity of O(n²). The space complexity is O(1) (excluding the output), making this approach both time and space efficient for most practical purposes.
Approach 3: Dynamic Programming
Dynamic programming (DP) offers another O(n²) solution but with O(n²) space. The idea is to build a table dp[i][j] that is True if the substring s[i:j+1] is a palindrome. We fill the table based on the observation that a substring is a palindrome if its outer characters match and the inner substring is also a palindrome.
Implementation
def longest_palindrome_dp(s: str) -> str:
n = len(s)
if n == 0:
return ""
# dp[i][j] is True if s[i:j+1] is a palindrome
dp = [[False] * n for _ in range(n)]
start = 0
max_length = 1
# Every single character is a palindrome
for i in range(n):
dp[i][i] = True
# Check for two-character palindromes
for i in range(n - 1):
if s[i] == s[i + 1]:
dp[i][i + 1] = True
start = i
max_length = 2
# Check for palindromes of length 3 or more
for length in range(3, n + 1):
for i in range(n - length + 1):
j = i + length - 1
if s[i] == s[j] and dp[i + 1][j - 1]:
dp[i][j] = True
if length > max_length:
start = i
max_length = length
return s[start:start + max_length]
# Example usage
print(longest_palindrome_dp("babad")) # Output: "bab" or "aba"
print(longest_palindrome_dp("cbbd")) # Output: "bb"
print(longest_palindrome_dp("forgeeksskeegfor")) # Output: "geeksskeeg"
Complexity Analysis
The DP approach fills an n × n table, resulting in a time complexity of O(n²) and a space complexity of O(n²). While it matches the expand-around-center approach in time, the higher space usage makes it less ideal for memory-constrained environments. However, the DP formulation is valuable for understanding the problem's structure and is a stepping stone to more advanced techniques.
Approach 4: Manacher's Algorithm
For those seeking the optimal solution, Manacher's algorithm finds the longest palindromic substring in O(n) time. It achieves this by reusing information from previously computed palindromes to skip redundant comparisons. The algorithm preprocesses the string by inserting a special separator (like #) between characters to unify odd and even length cases.
Implementation
def longest_palindrome_manacher(s: str) -> str:
if not s:
return ""
# Transform s to handle even-length palindromes uniformly
# Example: "aba" -> "^#a#b#a#$"
transformed = "^#" + "#".join(s) + "#$"
n = len(transformed)
p = [0] * n # p[i] = radius of palindrome centered at i
center = 0
right = 0
for i in range(1, n - 1):
mirror = 2 * center - i
if i < right:
p[i] = min(right - i, p[mirror])
# Attempt to expand palindrome centered at i
while transformed[i + p[i] + 1] == transformed[i - p[i] - 1]:
p[i] += 1
# If palindrome centered at i expands past right,
# adjust center and right
if i + p[i] > right:
center = i
right = i + p[i]
# Find the maximum element in p
max_len = max(p)
center_index = p.index(max_len)
# Map back to original string
start = (center_index - max_len) // 2
return s[start:start + max_len]
# Example usage
print(longest_palindrome_manacher("babad")) # Output: "bab" or "aba"
print(longest_palindrome_manacher("cbbd")) # Output: "bb"
print(longest_palindrome_manacher("a")) # Output: "a"
Complexity Analysis
Manacher's algorithm runs in O(n) time and O(n) space. The key insight is that the algorithm never re-examines characters that have already been confirmed to be part of a palindrome, allowing it to achieve linear time. While powerful, the algorithm is complex and typically overkill for interview settings unless explicitly requested.
Comparing the Approaches
- Brute Force: O(n³) time, O(n) space — simple but impractical for large inputs.
- Expand Around Center: O(n²) time, O(1) space — the best balance of simplicity and efficiency for interviews.
- Dynamic Programming: O(n²) time, O(n²) space — educational value but memory-heavy.
- Manacher's Algorithm: O(n) time, O(n) space — optimal but complex to implement and explain.
Best Practices
Handle Edge Cases Early
Always check for empty strings, single-character strings, and strings with no palindromes longer than one character. These cases are easy to overlook but are common in test suites.
def longest_palindrome_safe(s: str) -> str:
if not s or len(s) == 1:
return s
# ... proceed with chosen algorithm
Choose the Right Approach for the Context
In an interview, the expand-around-center approach is usually the sweet spot: it is efficient, easy to explain, and demonstrates strong problem-solving skills. Reserve Manacher's algorithm for situations where linear time is a hard requirement or when you want to showcase advanced knowledge.
Use Python's Slicing Wisely
Python's slicing syntax (s[i:j]) is concise and readable, but be mindful that it creates a new string. For performance-critical code, consider returning start and length indices instead of the substring itself, and slice only once at the end.
Write Test Cases
Verify your solution against a variety of inputs, including edge cases:
test_cases = [
("babad", ["bab", "aba"]),
("cbbd", ["bb"]),
("a", ["a"]),
("ac", ["a", "c"]),
("", [""]),
("racecar", ["racecar"]),
("abcdefg", ["a", "b", "c", "d", "e", "f", "g"]),
("aaaa", ["aaaa"]),
]
for s, expected in test_cases:
result = longest_palindrome_expand(s)
assert result in expected, f"Failed for '{s}': got '{result}'"
print("All tests passed!")
Optimize for Readability First
Premature optimization can make code harder to maintain and debug. Start with a clear, correct implementation, then optimize only if profiling reveals a bottleneck. The expand-around-center approach is often fast enough for strings up to a few thousand characters.
Common Pitfalls
- Off-by-one errors: When expanding around a center, ensure your bounds checks use
>= 0and< len(s)correctly. - Forgetting even-length palindromes: Many beginners only check single-character centers and miss cases like "abba".
- Returning the wrong substring: When multiple palindromes of the same maximum length exist, any valid answer is acceptable, but make sure your code returns one of them consistently.
- Ignoring empty input: Always handle the case where the input string is empty to avoid index errors.
Conclusion
The Longest Palindromic Substring problem is a rich exercise that scales from a simple brute-force solution to the elegant linear-time Manacher's algorithm. For most practical and interview scenarios, the expand-around-center approach offers the best tradeoff between efficiency, clarity, and ease of implementation. By understanding each approach's tradeoffs, handling edge cases diligently, and writing thorough test cases, you will be well-equipped to tackle this problem and similar string-manipulation challenges in Python. Mastering this problem not only prepares you for technical interviews but also deepens your appreciation for algorithm design and the thoughtful use of Python's language features.