LeetCode-in-All

5. Longest Palindromic Substring

Medium

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

Example 1:

Input: s = “babad”

Output: “bab” Note: “aba” is also a valid answer.

Example 2:

Input: s = “cbbd”

Output: “bb”

Example 3:

Input: s = “a”

Output: “a”

Example 4:

Input: s = “ac”

Output: “a”

Constraints:

Solution

object Solution {
    def longestPalindrome(s: String): String = {
        val newStr = new Array[Char](s.length * 2 + 1)
        newStr(0) = '#'
        for (i <- 0 until s.length) {
            newStr(2 * i + 1) = s.charAt(i)
            newStr(2 * i + 2) = '#'
        }

        val dp = new Array[Int](newStr.length)
        var friendCenter = 0
        var friendRadius = 0
        var lpsCenter = 0
        var lpsRadius = 0

        for (i <- 0 until newStr.length) {
            dp(i) =
                if (friendCenter + friendRadius > i)
                    Math.min(dp(friendCenter * 2 - i), (friendCenter + friendRadius) - i)
                else
                    1

            while (i + dp(i) < newStr.length
                && i - dp(i) >= 0
                && newStr(i + dp(i)) == newStr(i - dp(i))) {
                dp(i) += 1
            }

            if (friendCenter + friendRadius < i + dp(i)) {
                friendCenter = i
                friendRadius = dp(i)
            }

            if (lpsRadius < dp(i)) {
                lpsCenter = i
                lpsRadius = dp(i)
            }
        }

        s.substring((lpsCenter - lpsRadius + 1) / 2, (lpsCenter + lpsRadius - 1) / 2)
    }
}