5 Best Ways to Find the Length of the Longest Palindromic Substring in Python

Rate this post

πŸ’‘ Problem Formulation: Given a string, the problem involves finding the length of the longest substring which is also a palindrome. A palindrome is a string that reads the same backward as forward. For example, given the input "babad", the longest palindromic substring is "bab" (or "aba"), with a length of 3.

Method 1: Expand Around Center

The expand around center method works by considering each character in the string as the center of possible odd or even length palindromes and expands outwards to find the length of the longest palindromic substring at each center. Time complexity is O(n^2).

Here’s an example:

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

def longest_palindrome(s):
    start, end = 0, 0
    for i in range(len(s)):
        len1 = expand_around_center(s, i, i)
        len2 = expand_around_center(s, i, i + 1)
        max_len = max(len1, len2)
        if max_len > end - start:
            start = i - (max_len - 1) // 2
            end = i + max_len // 2
    return end - start + 1

print(longest_palindrome("babad"))

Output:

3

This code snippet defines two functions. expand_around_center() is a helper function that finds the palindrome length with respect to a central point (or points, for even-length palindromes). The longest_palindrome() function then uses this helper to iterate through each character in the string, checking for the longest palindrome centered at that character.

Method 2: Dynamic Programming

Dynamic programming solves problems by breaking them down into simpler subproblems. For finding the longest palindromic substring, a 2D table can be used to store palindromic truth values and updated via the principle of string comparison. This method has O(n^2) time and space complexity.

Here’s an example:

def longest_palindrome_dp(s):
    n = len(s)
    table = [[False for x in range(n)] for y in range(n)]
    max_length = 1
    start = 0

    for i in range(n):
        table[i][i] = True

    for i in range(n - 1):
        if s[i] == s[i + 1]:
            table[i][i + 1] = True
            start = i
            max_length = 2

    for k in range(3, n + 1):
        for i in range(n - k + 1):
            j = i + k - 1
            if s[i] == s[j] and table[i + 1][j - 1]:
                table[i][j] = True
                start = i
                max_length = k

    return max_length

print(longest_palindrome_dp("babad"))

Output:

3

The function longest_palindrome_dp() initializes a table to store the truth values of substring palindromes. It then fills this table using dynamic programming concepts to keep track of the longest palindromic substring seen so far, and its starting index, returning the length of this substring in the end.

Method 3: Manacher’s Algorithm

Manacher’s Algorithm is an optimized way to find the longest palindromic substring in linear time, O(n). It cleverly avoids redundant computations by using already computed palindromic information to find new palindromes around a central character.

Here’s an example:

# This is a simplified implementation of Manacher's Algorithm.
# For a complete implementation, additional code is required.

def longest_palindrome_manacher(s):
    # The provided code snippet is for illustrative purposes
    # and does not contain the full implementation of Manacher's Algorithm,
    # which would include the transformation of the string (adding separators) and more.
    pass

# Due to the complexity of Manacher's Algorithm,
# a full implementation example is not provided here.

Manacher’s Algorithm involves quite detailed coding which is beyond the scope of this short example. It typically includes preprocessing the string and then iterating through the modified string while maintaining a few arrays to remember the longest palindromic substrings found so far.

Method 4: Brute Force

The brute force method systematically checks every possible substring to see if it is a palindrome, and if so, whether it is longer than the current longest. Due to its simplicity, it is straightforward but highly inefficient with O(n^3) time complexity.

Here’s an example:

def longest_palindrome_bruteforce(s):
    max_length = 0
    for i in range(len(s)):
        for j in range(i, len(s)):
            substring = s[i:j+1]
            if substring == substring[::-1]:
                max_length = max(max_length, j - i + 1)
    return max_length

print(longest_palindrome_bruteforce("babad"))

Output:

3

The longest_palindrome_bruteforce() function iteratively selects all possible substrings of the input string and checks if each substring is a palindrome. If it finds a palindrome, it updates the maximum length found so far.

Bonus One-Liner Method 5: Pythonic Brute Force

A pythonic one-liner for brute force uses nested list comprehension and the max function to find the longest palindromic substring. However, it’s still O(n^3) time complexity and not efficient for large strings.

Here’s an example:

longest_palindrome = max((s[i:j+1] for i in range(len(s)) for j in range(i, len(s)) if s[i:j+1] == s[i:j+1][::-1]), key=len)
print(len(longest_palindrome))

Output:

3

This one-liner creates a generator expression that iterates over all possible substrings and filters out the palindromic ones. It then finds the longest palindrome by length and prints its length.

Summary/Discussion

  • Method 1: Expand Around Center. This method is intuitive and has a good time complexity of O(n^2). Its strength lies in its relative ease of implementation and no extra space requirement except for constant variables. Its weakness is that it’s not the fastest possible solution.
  • Method 2: Dynamic Programming. This method is systematic with a decent time complexity of O(n^2), but it uses O(n^2) space, which can be a drawback for very long strings. It’s more complex than method 1 but builds an understanding of subproblem optimization.
  • Method 3: Manacher’s Algorithm. Arguably the best in terms of time complexity, O(n), this method is also the most complex to understand and implement. Highly efficient for long strings, its downside is its algorithmic complexity.
  • Method 4: Brute Force. Brute force is simple but highly inefficient with O(n^3) time complexity. It’s not practical for large strings but can be useful for teaching purposes or when performance is not an issue.
  • Bonus Method 5: Pythonic Brute Force. This method is concise and uses Python’s powerful list comprehensions but shares the same inefficiency as the regular brute force method.