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

Anonymous

· 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
A

Anonymous

· 4 years ago

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

Show 2 replies

Reading Progress

0%

Vote for new content