Press n or j to go to the next uncovered block, b, p or k for the previous block.
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 | 10x 10x 10x 10000x 10x 1027x 10x 1018x 1002x 1002x 1002x 10x 1010x 498523x 498523x 498506x 498506x 498506x 10x | export default function longestPalindrome(s: string): string {
const n = s.length
let longestBegin = 0
let maxLen = 1
const dp = Array.from(Array.from({ length: 1000 }), () => Array.from<boolean>({ length: 1000 }).fill(false))
// Single character is palindrome
for (let i = 0; i < n; i++)
dp[i][i] = true
// Two repeat characters is palindrome
for (let i = 0; i < n - 1; i++) {
if (s.charAt(i) === s.charAt(i + 1)) {
dp[i][i + 1] = true
longestBegin = i
maxLen = 2
}
}
// Calculate isPalindrome(i, j)
// Length of palindrome start from `3` to `n`
for (let len = 3; len <= n; len++) {
for (let i = 0; i < n - len + 1; i++) {
const j = i + len - 1
if (s.charAt(i) === s.charAt(j) && dp[i + 1][j - 1]) {
dp[i][j] = true
longestBegin = i
maxLen = len
}
}
}
return s.slice(longestBegin, longestBegin + maxLen)
}
|