# 27.10.2023 [5. Longest Palindromic Substring]

Longest palindrome substring

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
    }