Longest Palindromic Substring Program (Leetcode)

Longest Palindromic Substring Program (Leetcode):

Given a string s, return the longest palindromic substring in s.

Example 1:

Input: s = "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

Input: s = "cbbd"
Output: "bb"

Example 3:

Input: s = "a"
Output: "a"

Example 4:

Input: s = "ac"
Output: "a"

 

Constraints:

• 1 <= s.length <= 1000
• s consist of only digits and English letters (lower-case and/or upper-case).

class Solution:
    def longestPalindrome(self, s: str) -> str:
        length = len(s)
        if length == 0:
            return ''
        
        dp = [[0]*length for j in range(length)]
        for i in range(length):
            dp[i][i] = 1    
  
        count = length
        val = s[0]
        for i in range(1, length):
            x = 0
            y = i
            for j in range(i, length):
                if count > (2 * length - 1):
                    if s[x] == s[y] and dp[x + 1][y - 1] == 1:
                        dp[x][y] = 1
                        val = s[x: y + 1]
                else:
                    if s[x] == s[y]:
                        dp[x][y] = 1
                        val = s[x: y + 1]       
                x += 1
                y += 1
                count += 1

        return val