Question

5. Longest Palindromic Substring

中文文档

Description

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.

Solutions

Solution 1: Dynamic Programming

We define $f[i][j]$ to represent whether the string $s[i..j]$ is a palindrome, initially $f[i][j] = true$.

Next, we define variables $k$ and $mx$, where $k$ represents the starting position of the longest palindrome, and $mx$ represents the length of the longest palindrome. Initially, $k = 0$, $mx = 1$.

Considering $f[i][j]$, if $s[i] = s[j]$, then $f[i][j] = f[i + 1][j - 1]$; otherwise, $f[i][j] = false$. If $f[i][j] = true$ and $mx < j - i + 1$, then we update $k = i$, $mx = j - i + 1$.

Since $f[i][j]$ depends on $f[i + 1][j - 1]$, we need to ensure that $i + 1$ is before $j - 1$, so we need to enumerate $i$ from large to small, and enumerate $j$ from small to large.

The time complexity is $O(n^2)$, and the space complexity is $O(n^2)$. Here, $n$ is the length of the string $s$.

class Solution:
  def longestPalindrome(self, s: str) -> str:
    n = len(s)
    f = [[True] * n for _ in range(n)]
    k, mx = 0, 1
    for i in range(n - 2, -1, -1):
      for j in range(i + 1, n):
        f[i][j] = False
        if s[i] == s[j]:
          f[i][j] = f[i + 1][j - 1]
          if f[i][j] and mx < j - i + 1:
            k, mx = i, j - i + 1
    return s[k : k + mx]

class Solution {
  public String longestPalindrome(String s) {
    int n = s.length();
    boolean[][] f = new boolean[n][n];
    for (var g : f) {
      Arrays.fill(g, true);
    }
    int k = 0, mx = 1;
    for (int i = n - 2; i >= 0; --i) {
      for (int j = i + 1; j < n; ++j) {
        f[i][j] = false;
        if (s.charAt(i) == s.charAt(j)) {
          f[i][j] = f[i + 1][j - 1];
          if (f[i][j] && mx < j - i + 1) {
            mx = j - i + 1;
            k = i;
          }
        }
      }
    }
    return s.substring(k, k + mx);
  }
}

class Solution {
public:
  string longestPalindrome(string s) {
    int n = s.size();
    vector<vector<bool>> f(n, vector<bool>(n, true));
    int k = 0, mx = 1;
    for (int i = n - 2; ~i; --i) {
      for (int j = i + 1; j < n; ++j) {
        f[i][j] = false;
        if (s[i] == s[j]) {
          f[i][j] = f[i + 1][j - 1];
          if (f[i][j] && mx < j - i + 1) {
            mx = j - i + 1;
            k = i;
          }
        }
      }
    }
    return s.substr(k, mx);
  }
};

func longestPalindrome(s string) string {
  n := len(s)
  f := make([][]bool, n)
  for i := range f {
    f[i] = make([]bool, n)
    for j := range f[i] {
      f[i][j] = true
    }
  }
  k, mx := 0, 1
  for i := n - 2; i >= 0; i-- {
    for j := i + 1; j < n; j++ {
      f[i][j] = false
      if s[i] == s[j] {
        f[i][j] = f[i+1][j-1]
        if f[i][j] && mx < j-i+1 {
          mx = j - i + 1
          k = i
        }
      }
    }
  }
  return s[k : k+mx]
}

function longestPalindrome(s: string): string {
  const n = s.length;
  const f: boolean[][] = Array(n)
    .fill(0)
    .map(() => Array(n).fill(true));
  let k = 0;
  let mx = 1;
  for (let i = n - 2; i >= 0; --i) {
    for (let j = i + 1; j < n; ++j) {
      f[i][j] = false;
      if (s[i] === s[j]) {
        f[i][j] = f[i + 1][j - 1];
        if (f[i][j] && mx < j - i + 1) {
          mx = j - i + 1;
          k = i;
        }
      }
    }
  }
  return s.slice(k, k + mx);
}

impl Solution {
  pub fn longest_palindrome(s: String) -> String {
    let (n, mut ans) = (s.len(), &s[..1]);
    let mut dp = vec![vec![false; n]; n];
    let data: Vec<char> = s.chars().collect();

    for end in 1..n {
      for start in 0..=end {
        if data[start] == data[end] {
          dp[start][end] = end - start < 2 || dp[start + 1][end - 1];
          if dp[start][end] && end - start + 1 > ans.len() {
            ans = &s[start..=end];
          }
        }
      }
    }
    ans.to_string()
  }
}

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function (s) {
  const n = s.length;
  const f = Array(n)
    .fill(0)
    .map(() => Array(n).fill(true));
  let k = 0;
  let mx = 1;
  for (let i = n - 2; i >= 0; --i) {
    for (let j = i + 1; j < n; ++j) {
      f[i][j] = false;
      if (s[i] === s[j]) {
        f[i][j] = f[i + 1][j - 1];
        if (f[i][j] && mx < j - i + 1) {
          mx = j - i + 1;
          k = i;
        }
      }
    }
  }
  return s.slice(k, k + mx);
};

public class Solution {
  public string LongestPalindrome(string s) {
    int n = s.Length;
    bool[,] f = new bool[n, n];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; ++j) {
        f[i, j] = true;
      }
    }
    int k = 0, mx = 1;
    for (int i = n - 2; i >= 0; --i) {
      for (int j = i + 1; j < n; ++j) {
        f[i, j] = false;
        if (s[i] == s[j]) {
          f[i, j] = f[i + 1, j - 1];
          if (f[i, j] && mx < j - i + 1) {
            mx = j - i + 1;
            k = i;
          }
        }
      }
    }
    return s.Substring(k, mx);
  }
}

import std/sequtils

proc longestPalindrome(s: string): string =
  let n: int = s.len()
  var
  dp = newSeqWith[bool](n, newSeqWith[bool](n, false))
  start: int = 0
  mx: int = 1

  for j in 0 ..< n:
  for i in 0 .. j:
    if j - i < 2:
    dp[i][j] = s[i] == s[j]
    else:
    dp[i][j] = dp[i + 1][j - 1] and s[i] == s[j]

    if dp[i][j] and mx < j - i + 1:
    start = i
    mx = j - i + 1

  result = s[start ..< start+mx]

Solution 2: Enumerate Palindrome Midpoint

We can enumerate the midpoint of the palindrome, spread to both sides, and find the longest palindrome.

The time complexity is $O(n^2)$, and the space complexity is $O(1)$. Here, $n$ is the length of the string $s$.

class Solution:
  def longestPalindrome(self, s: str) -> str:
    def f(l, r):
      while l >= 0 and r < n and s[l] == s[r]:
        l, r = l - 1, r + 1
      return r - l - 1

    n = len(s)
    start, mx = 0, 1
    for i in range(n):
      a = f(i, i)
      b = f(i, i + 1)
      t = max(a, b)
      if mx < t:
        mx = t
        start = i - ((t - 1) >> 1)
    return s[start : start + mx]

class Solution {
  private String s;
  private int n;

  public String longestPalindrome(String s) {
    this.s = s;
    n = s.length();
    int start = 0, mx = 1;
    for (int i = 0; i < n; ++i) {
      int a = f(i, i);
      int b = f(i, i + 1);
      int t = Math.max(a, b);
      if (mx < t) {
        mx = t;
        start = i - ((t - 1) >> 1);
      }
    }
    return s.substring(start, start + mx);
  }

  private int f(int l, int r) {
    while (l >= 0 && r < n && s.charAt(l) == s.charAt(r)) {
      --l;
      ++r;
    }
    return r - l - 1;
  }
}

class Solution {
public:
  string longestPalindrome(string s) {
    int n = s.size();
    int start = 0, mx = 1;
    auto f = [&](int l, int r) {
      while (l >= 0 && r < n && s[l] == s[r]) {
        l--, r++;
      }
      return r - l - 1;
    };
    for (int i = 0; i < n; ++i) {
      int a = f(i, i);
      int b = f(i, i + 1);
      int t = max(a, b);
      if (mx < t) {
        mx = t;
        start = i - (t - 1 >> 1);
      }
    }
    return s.substr(start, mx);
  }
};

func longestPalindrome(s string) string {
  n := len(s)
  start, mx := 0, 1
  f := func(l, r int) int {
    for l >= 0 && r < n && s[l] == s[r] {
      l, r = l-1, r+1
    }
    return r - l - 1
  }
  for i := range s {
    a, b := f(i, i), f(i, i+1)
    t := max(a, b)
    if mx < t {
      mx = t
      start = i - ((t - 1) >> 1)
    }
  }
  return s[start : start+mx]
}

impl Solution {
  pub fn is_palindrome(s: &str) -> bool {
    let mut chars = s.chars();
    while let (Some(c1), Some(c2)) = (chars.next(), chars.next_back()) {
      if c1 != c2 {
        return false;
      }
    }
    true
  }

  pub fn longest_palindrome(s: String) -> String {
    let size = s.len();
    let mut ans = &s[..1];
    for i in 0..size - 1 {
      for j in (i + 1..size).rev() {
        if ans.len() > j - i + 1 {
          break;
        }
        if Solution::is_palindrome(&s[i..=j]) {
          ans = &s[i..=j];
        }
      }
    }
    return ans.to_string();
  }
}

class Solution {
  /**
   * @param string $s
   * @return string
   */
  function longestPalindrome($s) {
    $start = 0;
    $maxLength = 0;

    for ($i = 0; $i < strlen($s); $i++) {
      $len1 = $this->expandFromCenter($s, $i, $i);
      $len2 = $this->expandFromCenter($s, $i, $i + 1);

      $len = max($len1, $len2);

      if ($len > $maxLength) {
        $start = $i - intval(($len - 1) / 2);
        $maxLength = $len;
      }
    }

    return substr($s, $start, $maxLength);
  }

  function expandFromCenter($s, $left, $right) {
    while ($left >= 0 && $right < strlen($s) && $s[$left] === $s[$right]) {
      $left--;
      $right++;
    }

    return $right - $left - 1;
  }
}