Longest Palindromic Substring
January 4, 2024
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 indexi
toj
is a palindrome.
Algorithm Steps: #
 Create a 2D array
dp
with dimensionsn x n
wheren
is the length of the string, initialized toFalse
.  Set every
dp[i][i]
toTrue
(since every single character is a palindrome).  Check for palindromic substrings of length 2 and update
dp
accordingly.  For substrings of length greater than 2, use the formula:
dp[i][j] = dp[i + 1][j  1] && s[i] == s[j]
.  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 2dimensional 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 twodimensional space. In the context of the Longest Palindromic Substring problem, here’s the rationale for using a 2D DP array:

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 indexi
and ending at indexj
is a palindrome. This direct mapping of subproblems to array cells makes the approach intuitive. 
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.

Bottomup Approach: The problem is solved in a bottomup 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 twodimensional table.

Logical Progression: In the DP array, the dependency of
dp[i][j]
is usually on cells likedp[i+1][j1]
,dp[i][j1]
, ordp[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. 
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 bottomup approach to solving the problem.