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
52
53
54
class Solution {
 public:
  string longestPalindrome(string s) {
    // '@' and '$' signs serve as sentinels appended to each end to avoid bounds
    // checking.
    const string& t = join('@' + s + '$', '#');
    const int n = t.length();
    // t[i - maxExtends[i]..i) ==
    // t[i + 1..i + maxExtends[i]]
    vector<int> maxExtends(n);
    int center = 0;

    for (int i = 1; i < n - 1; ++i) {
      const int rightBoundary = center + maxExtends[center];
      const int mirrorIndex = center - (i - center);
      maxExtends[i] =
          rightBoundary > i && min(rightBoundary - i, maxExtends[mirrorIndex]);

      // Attempt to expand the palindrome centered at i.
      while (t[i + 1 + maxExtends[i]] == t[i - 1 - maxExtends[i]])
        ++maxExtends[i];

      // If a palindrome centered at i expand past `rightBoundary`, adjust
      // center based on expanded palindrome.
      if (i + maxExtends[i] > rightBoundary)
        center = i;
    }

    // Find `maxExtend` and `bestCenter`.
    int maxExtend = 0;
    int bestCenter = -1;

    for (int i = 0; i < n; ++i)
      if (maxExtends[i] > maxExtend) {
        maxExtend = maxExtends[i];
        bestCenter = i;
      }

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

 private:
  string join(const string& s, char c) {
    string joined;
    for (int i = 0; i < s.length(); ++i) {
      joined += s[i];
      if (i != s.length() - 1)
        joined += c;
    }
    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
class Solution {
  public String longestPalindrome(String s) {
    // '@' and '$' signs serve as sentinels appended to each end to avoid bounds
    // checking.
    final String t = join('@' + s + '$', '#');
    final int n = t.length();
    // t[i - maxExtends[i]..i) ==
    // t[i + 1..i + maxExtends[i]]
    int[] maxExtends = new int[n];
    int center = 0;

    for (int i = 1; i < n - 1; ++i) {
      final int rightBoundary = center + maxExtends[center];
      final int mirrorIndex = center - (i - center);
      maxExtends[i] =
          rightBoundary > i && Math.min(rightBoundary - i, maxExtends[mirrorIndex]) > 0 ? 1 : 0;

      // Attempt to expand the palindrome centered at i.
      while (t.charAt(i + 1 + maxExtends[i]) == t.charAt(i - 1 - maxExtends[i]))
        ++maxExtends[i];

      // If a palindrome centered at i expand past `rightBoundary`, adjust
      // center based on expanded palindrome.
      if (i + maxExtends[i] > rightBoundary)
        center = i;
    }

    // Find `maxExtend` and `bestCenter`.
    int maxExtend = 0;
    int bestCenter = -1;

    for (int i = 0; i < n; ++i)
      if (maxExtends[i] > maxExtend) {
        maxExtend = maxExtends[i];
        bestCenter = i;
      }

    return s.substring((bestCenter - maxExtend) / 2, (bestCenter + maxExtend) / 2);
  }

  private String join(final String s, char c) {
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < s.length(); ++i) {
      sb.append(s.charAt(i));
      if (i != s.length() - 1)
        sb.append(c);
    }
    return sb.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:
    # '@' and '$' signs serve as sentinels appended to each end to avoid bounds
    # checking.
    t = '#'.join('@' + s + '$')
    n = len(t)
    # t[i - maxExtends[i]..i) ==
    # t[i + 1..i + maxExtends[i]]
    maxExtends = [0] * n
    center = 0

    for i in range(1, n - 1):
      rightBoundary = center + maxExtends[center]
      mirrorIndex = center - (i - center)
      maxExtends[i] = rightBoundary > i and \
          min(rightBoundary - i, maxExtends[mirrorIndex])

      # Attempt to expand the palindrome centered at i.
      while t[i + 1 + maxExtends[i]] == t[i - 1 - maxExtends[i]]:
        maxExtends[i] += 1

      # If a palindrome centered at i expand past `rightBoundary`, adjust
      # center based on expanded palindrome.
      if i + maxExtends[i] > rightBoundary:
        center = i

    # Find `maxExtend` and `bestCenter`.
    maxExtend, bestCenter = max((extend, i)
                                for i, extend in enumerate(maxExtends))
    return s[(bestCenter - maxExtend) // 2:(bestCenter + maxExtend) // 2]