【Leetcode】1682. Longest Palindromic Subsequence II

题目地址：

https://leetcode.com/problems/longest-palindromic-subsequence-ii/description/

给定一个长$n$字符串$s$，求其长度为偶数的最长回文子序列，要求除了正中间两个字母相等以外，其余位置相邻字母都不相等。题目保证$s$只含英文小写字母。只需返回长度。

设$f[l][r][c]$为$s[l:r]$中最长的两边字母为$c$的子序列长度。首先$f[l][r][c]$可以用$f[l+1][r][c],f[l][r-1][c]$更新；如果$s[l]=s[r]$，那么$f[l][c][.\ne s[l]]+2$都可以用来更新$f[l][r][c]$。最后返回${\max }_{c}f[l][r][c]$即可。代码如下：

class Solution {
 public:
  int longestPalindromeSubseq(string s) {
    int n = s.size(), f[n][n][26];
    memset(f, 0, sizeof f);
    for (int len = 2; len <= n; len++)
      for (int l = 0; l + len - 1 < n; l++) {
        int r = l + len - 1;
        for (int k = 0; k < 26; k++)
          f[l][r][k] = max(f[l + 1][r][k], f[l][r - 1][k]);
        if (s[l] == s[r]) {
          int x = s[l] - 'a';
          for (int k = 0; k < 26; k++)
            if (x != k) f[l][r][x] = max(f[l][r][x], 2 + f[l + 1][r - 1][k]);
        }
      }

    int res = 0;
    for (int len = 2; len <= n; len++)
      for (int l = 0; l + len - 1 < n; l++)
        for (int k = 0; k < 26; k++) res = max(res, f[l][l + len - 1][k]);

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

时空复杂度$O(n^2)$。