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”
Explanation: “aba” is also a valid answer.
Example 2:
Input: s = “cbbd”
Output: “bb”
Constraints:
1 <= s.length <= 1000sconsist of only digits and English letters.
Solution
func longestPalindrome(s string) string {
newStr := make([]byte, len(s)*2+1)
newStr[0] = '#'
for i := 0; i < len(s); i++ {
newStr[2*i+1] = s[i]
newStr[2*i+2] = '#'
}
dp := make([]int, len(newStr))
friendCenter, friendRadius := 0, 0
lpsCenter, lpsRadius := 0, 0
for i := 0; i < len(newStr); i++ {
if friendCenter+friendRadius > i {
dp[i] = min(dp[2*friendCenter-i], (friendCenter+friendRadius)-i)
} else {
dp[i] = 1
}
for i+dp[i] < len(newStr) && i-dp[i] >= 0 && newStr[i+dp[i]] == newStr[i-dp[i]] {
dp[i]++
}
if friendCenter+friendRadius < i+dp[i] {
friendCenter, friendRadius = i, dp[i]
}
if lpsRadius < dp[i] {
lpsCenter, lpsRadius = i, dp[i]
}
}
return s[(lpsCenter-lpsRadius+1)/2 : (lpsCenter+lpsRadius-1)/2]
}
func min(a, b int) int {
if a < b {
return a
}
return b
}