27.10.2023
5. Longest Palindromic Substring medium
blog post
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/383
Problem TLDR
Longest palindrome substring
Intuition
If dp[from][to]
answering whether substring s(from, to)
is a palindrome, then dp[from][to] = s[from] == s[to] && dp[from + 1][to - 1]
Approach
We can cleverly initialize the
dp
array to avoid some corner cases checks.It is better to store just two indices. For simplicity, let’s just do
substring
each time.
Complexity
Time complexity:
O(n^2)Space complexity:
O(n^2)
Code
fun longestPalindrome(s: String): String {
val dp = Array(s.length) { i -> BooleanArray(s.length) { i >= it } }
var res = s.take(1)
for (to in s.indices) for (from in to - 1 downTo 0) {
dp[from][to] = s[from] == s[to] && dp[from + 1][to - 1]
if (dp[from][to] && to - from + 1 > res.length)
res = s.substring(from, to + 1)
}
return res
}