5. Longest Palindromic Substring

Posted on Edited on In

5. Longest Palindromic Substring

Description

Difficulty: Medium

Related Topics: String, Dynamic Programming

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

Example 1:

1
2
3
Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Example 2:

1
2
Input: s = "cbbd"
Output: "bb"

Constraints:

  • 1 <= s.length <= 1000
  • s consist of only digits and English letters.

Hints/Notes

  • 2023/08/05
  • Use a helper function to get the longest palindromic string from one index
  • 0x3F’s solution(checked)

Solution

Language: C++

Manacher’s algorithm

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
public:
    string longestPalindrome(string s) {
        string manacher = "^#";
        for (auto& c : s) {
            manacher.push_back(c);
            manacher.push_back('#');
        }
        manacher.push_back('$');
        // the mapping between manacher and the original string:
        // a, b
        // 0, 1
        // =>
        // ^, #, a, #, b, #, $
        // 0, 1, 2, 3, 4, 5, 6
        // s[i] = t[(i + 1) * 2]
        // t[i] = s[i / 2 - 1]
        vector<int> halfLen(manacher.size() - 2, 0);
        int center = 0, right = 0, max_idx = 0;
        for (int i = 2; i < halfLen.size(); i++) {
            int len = 1;
            if (i < right) {
                len = min(right - i, halfLen[2 * center - i]);
            }
            while (manacher[i + len] == manacher[i - len]) {
                if (i + len > right) {
                    right = i + len;
                    center = i;
                }
                len++;
            }
            halfLen[i] = len;
            if (len > halfLen[max_idx]) {
                max_idx = i;
            }
        }
        int hl = halfLen[max_idx];
        // in fact we should use hl - 2, because manacher[i + len] != manacher[i - len] and the boundary is '#'
        // so the range in manacher is [max_idx - hl + 2, max_idx + hl - 2]
        // the range in origin is [(max_idx - hl) / 2, (max_idx + hl) / 2 - 2];
        return s.substr((max_idx - hl) / 2, hl - 1);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    string longestPalindrome(string s) {
        string res;
        for (int i = 0; i < s.size(); i++) {
            string s1 = palindrom(s, i, i);
            string s2 = palindrom(s, i, i + 1);
            res = res.size() > s1.size() ? res : s1;
            res = res.size() > s2.size() ? res : s2;
        }
        return res;
    }

    string palindrom(string s, int left, int right) {
        while (left >= 0 && right < s.size()) {
            if (s[left] != s[right]) {
                break;
            }
            left--;
            right++;
        }
        return s.substr(left + 1, right - left - 1);
    }
};