Grokking Dynamic Programming Patterns for Coding Interviews
Vote

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!
S

Shan

· 4 years ago

Can you add the brute force, swapping the max for count does not work on the leetcode problem

Show 2 replies
Mohammed Dh Abbas

Mohammed Dh Abbas

· 2 years ago

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

    count = 0
    for i in range(0, len(st)):
      for j in range(i, len(st)):
        if is_palindrom(st, i, j):
            count += 1
    
    return count
Show 1 reply
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

A

alik.dudin

· 10 months ago

private int dyn(String st,int startIndex , int endIndex, Integer[][] dp){
    if(startIndex == endIndex){
        return 1;
    }
    if(startIndex>endIndex){
        return 0;
    }
    if(dp[startIndex][endIndex]!=null){
        return dp[startIndex][endIndex];
    }
    if(st.charAt(startIndex) == st.charAt(endIndex)&& endIndex-startIndex-1==dyn(st,startIndex+1,endIndex-1,dp)){
        dp[startIndex][endIndex] = 2+endIndex-startIndex-1;
        return dp[startIndex][endIndex];
    }else{
        dp[startIndex][endIndex] = Math.max(dyn(st,startIndex+1,endIndex,dp),dyn(st,startIndex,endIndex-1,dp));
    }
    return dp[startIndex][endIndex];
}