Grokking Dynamic Programming Patterns for Coding Interviews

0% completed

​

Solution: Longest Palindromic Substring

Problem Statement

Given a string, find the length of its Longest Palindromic Substring (LPS). In a palindromic string, elements read the same backward and forward.

Example 1:

Input: "abdbca"
Output: 3
Explanation: LPS is "bdb".

Example 2:

Input: = "cddpd"
Output: 3
Explanation: LPS is "dpd".

Example 3:

Input: = "pqr"
Output: 1
Explanation: LPS could be "p", "q" or "r".

Constraints:

  • 1 <= st.length <= 1000
  • st consists only of lowercase English letters.

Basic Solution

This problem follows the "Longest Palindromic Subsequence" pattern

.....

.....

.....

Like the course? Get enrolled and start learning!
Vikas Mishra

Vikas Mishra

· a year ago

Generally this question is solved totally different way. using 2 for loops. Is that expected or we can solve this question in similar way as we found longest palindromic substring