LeetCode Entry

5. Longest Palindromic Substring

27.10.2023 medium 2023 kotlin

Longest palindrome substring

5. Longest Palindromic Substring medium blog post substack image.png Golf version image.png

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
    }