5. Longest Palindromic Substring

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 <= 1000
• s consist of only digits and English letters.

解法一：暴力解

沒打算用暴力解，因此跳過

解法二：從中間擴增

時間複雜度：$O(n^2)$

原因：同時要考奇數、偶數情況

原理

程式碼

class Solution {
    public String longestPalindrome(String s) {
        if (s.length() == 1 || s.length() == 0) {
            return s;
        }
        String maxStr = "";
 
        for (int i = 0; i < s.length(); i++) {
            String first = expendFromCenter(s, i, i);
            String sec = expendFromCenter(s, i, i + 1);
 
            if (first.length() > maxStr.length()) {
                maxStr = first;
            }
            if (sec.length() > maxStr.length()) {
                maxStr = sec;
            }
        }
        return maxStr;
    }
    public String expendFromCenter(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return s.substring(left + 1, right);
    }
}

解法三：Manacher’s Algorithm

好處：當input為偶數時，不用跑兩次中心點，因此對比解法二：從中間擴增時間複雜度較少。

時間複雜度：$O(n)$

Manacher’s Algorithm – Linear Time Longest Palindromic Substring – Part 1

[演算法] Manacher’s Algorithm 筆記](https://medium.com/hoskiss-stand/manacher-299cf75db97e) longest palindromic substring 演算法整理 (Manacher’s algorithm)