[LeetCode] Longest Palindromic Substring (Java)

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.


This is a very basic dynamic programming problem. We use a 2-D boolean array P to save whether a substring of s is palindromic. We start from substring of length of 1 to length of length of s. If s[i] = s[j] and P[i+1][j-1] is true, we know that we need to update P[i][j] to true. In addition, if j – i <= 2, it means the length of this substring is only 1 or 2, so we can directly update P[i][j] to true.

To return the longest palindromic substring, we need to save the start point and the maximum length of the palindromic substring during our processing.


In this code, in fact, (k + 1) is the length of the substring. Writing in this way will be more convenient.


We need to check every substring in this string. The time complexity is $O(n^2)$, which is the same as the space complexity.