Longest Palindromic Substring

Longest Palindromic Substring

January 4, 2024
medium
dynamic programming

Problem #

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

Example:

  • Input: s = "babad"
  • Output: One of "bab" or "aba" (since both are valid longest palindromic substrings).

Solution #

Algorithm Used: #

  • Dynamic Programming

Solution Approach: #

  • The approach is to build a table that represents substrings of the given string. The table will be filled in a way that table[i][j] will be true if the substring from index i to j is a palindrome.

Algorithm Steps: #

  1. Create a 2D array dp with dimensions n x n where n is the length of the string, initialized to False.
  2. Set every dp[i][i] to True (since every single character is a palindrome).
  3. Check for palindromic substrings of length 2 and update dp accordingly.
  4. For substrings of length greater than 2, use the formula: dp[i][j] = dp[i + 1][j - 1] && s[i] == s[j].
  5. Keep track of the longest palindrome found.

Python Code: # 

def longestPalindrome(s):
    n = len(s)
    if n < 2:
        return s

    dp = [[False] * n for _ in range(n)]
    start, max_length = 0, 1

    # Every single character is a palindrome
    for i in range(n):
        dp[i][i] = True

    # Check for palindromic substrings of length 2
    for i in range(n - 1):
        if s[i] == s[i + 1]:
            dp[i][i + 1] = True
            start = i
            max_length = 2

    # Check for lengths greater than 2
    for length in range(3, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if dp[i + 1][j - 1] and s[i] == s[j]:
                dp[i][j] = True
                start = i
                max_length = length

    return s[start:start + max_length]

# Example Usage
print(longestPalindrome("babad"))

Time Complexity: #

  • O(n^2), where n is the length of the string. The nested loops go through every substring of the string.

Space Complexity: #

  • O(n^2), for the dp array storing information about every substring.

Solution Analysis #

Using a 2-dimensional dynamic programming (DP) array is a strategic choice when dealing with problems where the solution involves breaking down the problem into smaller subproblems, and these subproblems can be represented in a two-dimensional space. In the context of the Longest Palindromic Substring problem, here’s the rationale for using a 2D DP array:

  1. Representation of Subproblems: Each cell in the 2D DP array, dp[i][j], represents a specific subproblem. In this case, it indicates whether the substring of the input string starting at index i and ending at index j is a palindrome. This direct mapping of subproblems to array cells makes the approach intuitive.

  2. Memory Optimization: Although a 2D DP array increases space complexity, it significantly optimizes the solution’s time complexity. Without the DP array, you might end up recalculating the palindromic status of the same substring multiple times, leading to a much higher time complexity. The 2D DP array allows us to store these results and access them in constant time.

  3. Bottom-up Approach: The problem is solved in a bottom-up manner, where we first solve the smaller subproblems (substrings of length 1 and 2) and use these solutions to build up to the solution of the larger problem (longer substrings). This process is naturally suited to being represented in a two-dimensional table.

  4. Logical Progression: In the DP array, the dependency of dp[i][j] is usually on cells like dp[i+1][j-1], dp[i][j-1], or dp[i+1][j]. This forms a pattern where the solution to a problem at a specific cell depends on the solutions to problems in cells that have already been solved, adhering to the principle of dynamic programming.

  5. Ease of Iteration and Updating: The 2D DP array allows for efficient iteration over all possible substrings in the string, and the update rule (dp[i][j] = dp[i + 1][j - 1] && s[i] == s[j]) is straightforward to implement in a nested loop structure.

In summary, the use of a 2D DP array in problems like finding the longest palindromic substring provides a clear and efficient method to store and update the results of subproblems, thereby facilitating an optimized bottom-up approach to solving the problem.