Skip to content

5. Longest Palindromic Substring 👍

Approach 1: Naive

  • Time: $O(n^2)$
  • Space: $O(n)$
 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
class Solution {
 public:
  string longestPalindrome(string s) {
    if (s.empty())
      return "";

    // (start, end) indices of the longest palindrome in s
    pair<int, int> indices{0, 0};

    for (int i = 0; i < s.length(); ++i) {
      const auto [l1, r1] = extend(s, i, i);
      if (r1 - l1 > indices.second - indices.first)
        indices = {l1, r1};
      if (i + 1 < s.length() && s[i] == s[i + 1]) {
        const auto [l2, r2] = extend(s, i, i + 1);
        if (r2 - l2 > indices.second - indices.first)
          indices = {l2, r2};
      }
    }

    return s.substr(indices.first, indices.second - indices.first + 1);
  }

 private:
  // Returns the (start, end) indices of the longest palindrome extended from
  // the substring s[i..j].
  pair<int, int> extend(const string& s, int i, int j) {
    for (; i >= 0 && j < s.length(); --i, ++j)
      if (s[i] != s[j])
        break;
    return {i + 1, j - 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
25
26
27
28
29
30
31
class Solution {
  public String longestPalindrome(String s) {
    if (s.isEmpty())
      return "";

    // (start, end) indices of the longest palindrome in s
    int[] indices = {0, 0};

    for (int i = 0; i < s.length(); ++i) {
      int[] indices1 = extend(s, i, i);
      if (indices1[1] - indices1[0] > indices[1] - indices[0])
        indices = indices1;
      if (i + 1 < s.length() && s.charAt(i) == s.charAt(i + 1)) {
        int[] indices2 = extend(s, i, i + 1);
        if (indices2[1] - indices2[0] > indices[1] - indices[0])
          indices = indices2;
      }
    }

    return s.substring(indices[0], indices[1] + 1);
  }

  // Returns the (start, end) indices of the longest palindrome extended from
  // the substring s[i..j].
  private int[] extend(final String s, int i, int j) {
    for (; i >= 0 && j < s.length(); --i, ++j)
      if (s.charAt(i) != s.charAt(j))
        break;
    return new int[] {i + 1, j - 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
25
26
27
28
29
30
class Solution:
  def longestPalindrome(self, s: str) -> str:
    if not s:
      return ''

    # (start, end) indices of the longest palindrome in s
    indices = [0, 0]

    def extend(s: str, i: int, j: int) -> tuple[int, int]:
      """
      Returns the (start, end) indices of the longest palindrome extended from
      the substring s[i..j].
      """
      while i >= 0 and j < len(s):
        if s[i] != s[j]:
          break
        i -= 1
        j += 1
      return i + 1, j - 1

    for i in range(len(s)):
      l1, r1 = extend(s, i, i)
      if r1 - l1 > indices[1] - indices[0]:
        indices = l1, r1
      if i + 1 < len(s) and s[i] == s[i + 1]:
        l2, r2 = extend(s, i, i + 1)
        if r2 - l2 > indices[1] - indices[0]:
          indices = l2, r2

    return s[indices[0]:indices[1] + 1]

Approach 2: Manacher

  • Time: $O(n)$
  • Space: $O(n)$
 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
44
45
46
47
48
49
50
51
class Solution {
 public:
  string longestPalindrome(string s) {
    const string t = join('@' + s + '$', /*delimiter=*/'#');
    const vector<int> p = manacher(t);
    int maxPalindromeLength = 0;
    int bestCenter = -1;

    for (int i = 0; i < p.size(); ++i)
      if (p[i] > maxPalindromeLength) {
        maxPalindromeLength = p[i];
        bestCenter = i;
      }

    const int l = (bestCenter - maxPalindromeLength) / 2;
    const int r = (bestCenter + maxPalindromeLength) / 2;
    return s.substr(l, r - l);
  }

 private:
  // Returns an array `p` s.t. `p[i]` is the length of the longest palindrome
  // centered at `t[i]`, where `t` is a string with delimiters and sentinels.
  vector<int> manacher(const string& t) {
    vector<int> p(t.length());
    int center = 0;
    for (int i = 1; i < t.length() - 1; ++i) {
      const int rightBoundary = center + p[center];
      const int mirrorIndex = center - (i - center);
      if (rightBoundary > i)
        p[i] = min(rightBoundary - i, p[mirrorIndex]);
      // Try to expand the palindrome centered at i.
      while (t[i + 1 + p[i]] == t[i - 1 - p[i]])
        ++p[i];
      // If a palindrome centered at i expands past `rightBoundary`, adjust
      // the center based on the expanded palindrome.
      if (i + p[i] > rightBoundary)
        center = i;
    }
    return p;
  }

  string join(const string& s, char delimiter) {
    string joined;
    for (int i = 0; i < s.length() - 1; ++i) {
      joined += s[i];
      joined += delimiter;
    }
    joined += s.back();
    return joined;
  }
};

 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
44
45
46
47
48
49
50
51
class Solution {
  public String longestPalindrome(String s) {
    final String t = join('@' + s + '$', /*delimiter=*/'#');
    final int[] p = manacher(t);
    int maxPalindromeLength = 0;
    int bestCenter = -1;

    for (int i = 0; i < p.length; ++i)
      if (p[i] > maxPalindromeLength) {
        maxPalindromeLength = p[i];
        bestCenter = i;
      }

    final int l = (bestCenter - maxPalindromeLength) / 2;
    final int r = (bestCenter + maxPalindromeLength) / 2;
    return s.substring(l, r);
  }

  // Returns an array `p` s.t. `p[i]` is the length of the longest palindrome
  // centered at `t[i]`, where `t` is a string with delimiters and sentinels.
  private int[] manacher(final String t) {
    int[] p = new int[t.length()];
    int center = 0;
    for (int i = 1; i < t.length() - 1; ++i) {
      int rightBoundary = center + p[center];
      int mirrorIndex = center - (i - center);
      if (rightBoundary > i)
        p[i] = Math.min(rightBoundary - i, p[mirrorIndex]);
      // Try to expand the palindrome centered at i.
      while (i + 1 + p[i] < t.length() && i - 1 - p[i] >= 0 &&
             t.charAt(i + 1 + p[i]) == t.charAt(i - 1 - p[i]))
        ++p[i];
      // If a palindrome centered at i expands past `rightBoundary`, adjust
      // the center based on the expanded palindrome.
      if (i + p[i] > rightBoundary) {
        center = i;
      }
    }
    return p;
  }

  private String join(final String s, char delimiter) {
    StringBuilder joined = new StringBuilder();
    for (int i = 0; i < s.length() - 1; ++i) {
      joined.append(s.charAt(i));
      joined.append(delimiter);
    }
    joined.append(s.charAt(s.length() - 1));
    return joined.toString();
  }
}

 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
class Solution:
  def longestPalindrome(self, s: str) -> str:
    t = '#'.join('@' + s + '$')
    p = self._manacher(t)
    maxPalindromeLength, bestCenter = max((extend, i)
                                          for i, extend in enumerate(p))
    l = (bestCenter - maxPalindromeLength) // 2
    r = (bestCenter + maxPalindromeLength) // 2
    return s[l:r]

  def _manacher(self, t: str) -> list[int]:
    """
    Returns an array `p` s.t. `p[i]` is the length of the longest palindrome
    centered at `t[i]`, where `t` is a string with delimiters and sentinels.
    """
    p = [0] * len(t)
    center = 0
    for i in range(1, len(t) - 1):
      rightBoundary = center + p[center]
      mirrorIndex = center - (i - center)
      if rightBoundary > i:
        p[i] = min(rightBoundary - i, p[mirrorIndex])
      # Try to expand the palindrome centered at i.
      while t[i + 1 + p[i]] == t[i - 1 - p[i]]:
        p[i] += 1
      # If a palindrome centered at i expands past `rightBoundary`, adjust
      # the center based on the expanded palindrome.
      if i + p[i] > rightBoundary:
        center = i
    return p