Grokking Dynamic Programming Patterns for Coding Interviews
Vote

0% completed

​

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.

Try it yourself

Try solving this question here:

.....

.....

.....

Like the course? Get enrolled and start learning!
S

Shan

· 4 years ago

This solution can easily be extended to cover the leetcode question https://leetcode.com/problems/longest-palindromic-substring/

You can replace the maxLength with the current longest found substring. Dethrone it as necessary.

Mohammed Dh Abbas

Mohammed Dh Abbas

· 2 years ago

class Solution:
  def findLPSLength(self, st):
    
    def is_palindrom(s, i, j):
      while i <= j:
        if s[i] != s[j]:
          return False
        i += 1
        j -= 1
      return True

    def dp(s, i, j, memo):
      if (i, j) in memo:
        return memo[(i, j)]

      if is_palindrom(s, i, j):
        return j - i + 1
      
      if i > j:
        return 0 

      result = max(dp(s, i + 1, j, memo), dp(s, i, j - 1, memo))
      
      memo[(i, j)] = result
      
      return result

    return dp(st, 0, len(st) - 1, {})