3504.子字符串连接后的最长回文串II

dp, greedy, https://leetcode.cn/problems/longest-palindrome-after-substring-concatenation-ii/

给你两个字符串 s 和 t。

你可以从 s 中选择一个子串（可以为空）以及从 t 中选择一个子串（可以为空），然后将它们 按顺序 连接，得到一个新的字符串。

返回可以由上述方法构造出的 最长 回文串的长度。

回文串 是指正着读和反着读都相同的字符串。

子字符串 是指字符串中的一个连续字符序列。

示例 1：

输入： s = "a", t = "a"

输出： 2

解释：

从 s 中选择 "a"，从 t 中选择 "a"，拼接得到 "aa"，这是一个长度为 2 的回文串。

示例 2：

输入： s = "abc", t = "def"

输出： 1

解释：

由于两个字符串的所有字符都不同，最长的回文串只能是任意一个单独的字符，因此答案是 1。

示例 3：

输入： s = "b", t = "aaaa"

输出： 4

解释：

可以选择 "aaaa" 作为回文串，其长度为 4。

示例 4：

输入： s = "abcde", t = "ecdba"

输出： 5

解释：

从 s 中选择 "abc"，从 t 中选择 "ba"，拼接得到 "abcba"，这是一个长度为 5 的回文串。

提示：

• 1 <= s.length, t.length <= 1000
• s 和 t 仅由小写英文字母组成。

class Solution:
    def longestPalindrome(self, s: str, t: str) -> int:
        # 反转 t，方便匹配 s 的前缀
        t = t[::-1]
        
        # 将字符转换为 ASCII 值数组，方便计算
        #s = [ord(c) for c in s]
        #t = [ord(c) for c in t]
        
        n, m = len(s), len(t)
        
        # 计算 s 和 t 反转的最长公共前缀长度 dp[i][j]
        dp = [[0] * (m + 1) for _ in range(n + 1)]
        for i in range(n - 1, -1, -1):
            for j in range(m - 1, -1, -1):
                if s[i] == t[j]:
                    dp[i][j] = dp[i + 1][j + 1] + 1
        
        def compute_palindrome_prefix(x):
            """
            计算 x 数组的最长回文前缀长度 res[i]。
            res[i] 代表从索引 i 开始的子串的最长回文子串长度。
            """
            length = len(x)
            res = [0] * (length + 1)
            
            # 计算奇数长度回文
            for center in range(length):
                left = right = center #比如 "aba" 以 'b' 为中心。
                while left >= 0 and right < length and x[left] == x[right]:
                    res[left] = max(res[left], right - left + 1)
                    left -= 1
                    right += 1
            
            # 计算偶数长度回文
            for center in range(1, length):
                left, right = center - 1, center
                while left >= 0 and right < length and x[left] == x[right]:
                    res[left] = max(res[left], right - left + 1)
                    left -= 1
                    right += 1
            
            return res
        
        # 计算 s 和 t 的最长回文前缀数组
        palindrome_s = compute_palindrome_prefix(s)
        palindrome_t = compute_palindrome_prefix(t)
        
        # 计算独立于拼接的最大回文长度
        max_palindrome_length = max(max(palindrome_s), max(palindrome_t))
        
        # 遍历 s 和 t 的匹配位置，尝试拼接形成更长的回文串
        for i in range(n):
            for j in range(m):
                if dp[i][j] > 0:  # 只考虑有公共前缀的情况
                    common_length = dp[i][j]
                    remaining_s = palindrome_s[i + common_length]
                    remaining_t = palindrome_t[j + common_length]
                    max_palindrome_length = max(
                        max_palindrome_length, 
                        common_length * 2 + max(remaining_s, remaining_t)
                    )
        
        return max_palindrome_length