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

Thinking

Checking every \(s[i..j]\) from the ends is \(O(n^3)\). \(n \le 10^3\) is tight and often times out.

The waste is rescanning each substring. A palindrome has optimal substructure: \(s[i..j]\) is a palindrome iff the two ends match and the inner \(s[i+1..j-1]\) already is one. Single characters are palindromes for free.

So we fill an interval table in dependency order instead of scanning repeatedly. \(f[i][j]\) reads a shorter inner cell, so that cell must already be known; while filling, \(k\) and \(mx\) remember the start and length of the best palindrome so far.

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\).

Solution 2: Enumerate Palindrome Midpoint

Thinking

Solution 1 is already \(O(n^2)\) time, but it still pays \(O(n^2)\) space. Each check only needs the inner layer, not the whole table.

A palindrome expands symmetrically from a center: grow while the two ends match. We must try both odd centers \((i,i)\) and even centers \((i,i+1)\), or we miss strings like "bb".

After expanding, recover the start from center \(i\) and length \(t\). Extra space drops to \(O(1)\).

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\).

Python3JavaC++GoRustC#PHP

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();
    }
}

public 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[l] == s[r]) {
            --l;
            ++r;
        }
        return r - l - 1;
    }
}

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;
    }
}

5. Longest Palindromic Substring

Description

Solutions

Solution 1: Dynamic Programming

Solution 2: Enumerate Palindrome Midpoint

Comments