# LeetCode 5. Longest Palindromic Substring

## Description

https://leetcode.com/problems/longest-palindromic-substring/description/

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example:

Example:

## Explanation

A palindromic string meets two criteria:

1. first and the last character are the same
2. the inner word between the first and the last character is a palindromic string

The basic idea is to use dynamic programming to determine whether a substring is palindromic string base on above criteria.

Need to be careful that when returning the result, the end index need to plus 1, because java substring method doesn’t include the ending index.

## 3 thoughts

1. Divya Singh says:

I have the same question in python but the platform accepts input only in this format. The problem is Test Case with 12 as length and abcbcabbacba as string is resulting in 12 and same string as output , it should be 8, bcabbacb. Can you tell where I misunderstood the logic and syntax. My code is as follows:

#input length, string
N=int(input())
w=input()

if w == ” or len(w)<=2:
print(len(w))
print(w)

if N<=5000:
isPallindrome = [[0]*N]*N
left=0
right=0

for j in range(1,N):
for i in range(0,j):
isInnerWordPallindrome = isPallindrome[i+1][j-1] or j-i right-left:
left = i
right = j

var1 = len(w[left:right+1])
var2 = w[left:right+1]
print(var1)
print(var2)