Solution: Longest Palindromic Substring
Let’s solve the Longest Palindromic Substring problem using the Dynamic Programming pattern.
Statement
Given a string s, return the longest palindromic substring in s.
Constraints
-
s.length -
sconsist of only digits and English letters.
Solution
So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which to follow based on considerations, such as time complexity and implementation constraints.
Naive approach
A naive approach to this problem is to find all possible substrings and select one longest palindromic substring. For example, consider the string “deed”, which contains 10 substrings: “d”, “e”, “e”, “d”, “de”, “ee”, “ed”, “dee”, “eed”, and “deed”. Out of these 10 substrings, six are palindromes: “d”, “e”, “e”, “d”, “ee”, and “deed”. Among these palindromes, the longest palindromic substring is “deed”.
We get the required result, but at what cost? Since we’re checking every possible substring, the total number of substrings in a string of length