Instead of directly jumping into the problem, Let’s understand, What is Longest Palindromic Substring and Dynamic Programming.
What is the Longest Palindromic Substring
Finding the longest substring within a given string that reads the same backwards as forward. A substring is a contiguous sequence of characters within a string.
A palindrome is a string that reads the same backwards as forward. For example, “madam“, “racecar“, and “a” are palindromes. The task is to identify the longest such sequence within a given string. To solve this problem we can use several methods, including dynamic programming, expanding around the centre, and Manacher’s algorithm. But in this article, we are using Dynamic Programming.
Let’s understand first what is Dynamic Programming (DP)
What is the Dynamic Programming (DP)
Dynamic Programming (DP) is a method for solving complex problems by breaking them down into smaller subproblems. It is particularly useful for optimization problems where the solution can be constructed efficiently by solving overlapping subproblems and storing their solutions.
Dynamic Programming divided into 4 Key Concepts
- Optimal Substructure
- Overlapping Subproblems
- Memoization
- Tabulation
Enough Talking about DP and Palindromic Substring. Let’s jump into problem.
Problem Statement
Given a string s, find the longest substring that is a palindrome.
Input
A string s of length nOutput
The longest palindromic substring in s.Constraints
1 ≤ n ≤ 1000Example Scenarios
Input: babad
Output: bab (or aba)To solve this problem using dynamic programming, we can use a 2D table to keep track of palindromic sub strings.
Code
Let’s see how can we solve this problem using python.
def longest_palindromic_substring(s):
n = len(s)
dp = [[False] * n for _ in range(n)]
start, max_length = 0, 1
for i in range(n):
dp[i][i] = True
for i in range(n - 1):
if s[i] == s[i + 1]:
dp[i][i + 1] = True
start = i
max_length = 2
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
start = i
max_length = length
return s[start:start + max_length]
# Example usage
print(longest_palindromic_substring("babad")) # Output: "bab" or "aba"
print(longest_palindromic_substring("cbbd")) # Output: "bb"Testing and Edge Cases
s = "a"-> Output:"a"s = "ac"-> Output:"a"or"c"s = "racecar"-> Output:"racecar"s = "forgeeksskeegfor"-> Output:"geeksskeeg"
Complexity Analysis
- Time Complexity: O(n^2)
- Space Complexity: O(n^2)