# Leetcode 5 - Longest palindrome substring

Note:

• DP:
• What does dp[i][j] should mean? Either length of palindrome or bool. But clearly, bool is the only way to obtain the longest palinrome.
• dp[i][j] means if s[i - j] is a palindrome.
• Because dp[i][j] depends on dp[i+1][j-1], we have to iterate i from big to small, j from small to big. Also, make sure j bigger than i.
• When j - i < 1. Compare the length.
• When j - i > 1, check dp[i+1][j-1].
• Center spread:
• For each single element or two adjacent elements, we spread the window if the two new nums on left end and right end are equal.
• Because there might be both single center or dual center, we have to do twice.

Question:

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

Example:

Code:

Center spread O(n^2)

DP, O(n^2)

Brute Force O(n^2)