题目描述

难度分:$1900$

输入长度$\leq 5 \times 10^4$的字符串$s$，只包含小写英文字母。

输出$s$的一个长度恰好为$100$的回文子序列。如果不存在这样的子序列，输出$s$的最长回文子序列。多解输出任意解。

注：子序列不一定连续。

输入样例$1$

bbbabcbbb

输出样例$1$

bbbcbbb

输入样例$2$

rquwmzexectvnbanemsmdufrg

输出样例$2$

rumenanemur

算法

动态规划

这个题我最先想到的就是最长回文子序列的动态规划解法，但是这个解法是$O(n^2)$的，实在不知道怎么去优化。这里就要思考为什么题目会让你输出长度为$100$的回文子序列？如果字符串$s$的长度$\geq 2600$，即便是$26$种字母都出现了个遍，也肯定会出现频数$\geq 100$的字母，把出现最多的字母挑$100$个出来就能构造出一个合法的解。那么$s$的长度$\lt 2600$的情况就可以用动态规划了。

状态定义

$dp[l][r]$表示子串$[l,r]$中的最大回文子序列长度。

状态转移

如果$s[l]$不作为回文子序列中的一个字母，就进行状态转移$dp[l][r]=dp[l+1][r]$。否则我们贪心地来构造这个回文子序列，找到$\gt l$最右的$s[l]$，可以预处理出一个映射$pos$，表示“字母$\rightarrow$该字母出现的索引列表”，从而二分$pos[s[l]]$确定这个位置$index$，然后状态转移$dp[l][r]=2+dp[l+1][index-1]$。两种情况选择较大值进行转移，$dp[l][r]=max(dp[l+1][r],2+dp[l+1][index-1])$。

获得最大回文子序列长度之后，利用$dp$矩阵把这个回文子序列构造出来，这个比较套路，用$dfs$倒着推就可以了。假设得到了一个长度为$sz$的回文串$ans$，分为以下两种情况得到最终答案：

1. 如果$sz$是奇数，那么去掉中间的字符，将$ans$分成长度相等的两段$left$和$right$。取$left$长度为$50$的后缀和$right$长度为$50$的前缀就能构造出来。
2. 如果$sz$是偶数，可以取中间一段回文，前面$start=\frac{sz-100}{2}$的长度就可以抛弃掉，从$ans$的$start$位置开始截取长度为$100$的子串就构造出了答案。

复杂度分析

时间复杂度

如果$s$的长度$\geq 2600$，遍历一遍$s$统计出每个字母的频数既可以构造出答案，时间复杂度为$O(n)$。如果$s$的长度$\lt 2600$，那么就走动态规划，状态数量为$O(n^2)$，单次转移需要进行一次二分，时间复杂度为$O(n^2log_2n)$。

空间复杂度

$pos$中需要存$O(n)$个索引，空间复杂度为$O(n)$。$dp$矩阵在$n \lt 2600$的情况下要存$O(n^2)$级别的状态，空间复杂度为$O(2600^2)$。在还原出$s$串的最长回文子序列时还需要一个标记数组$used$，它是$O(n)$大小的，$used[i]=$true的$s[i]$要被选到最长回文子序列中。对于$n \geq 2600$的情况，需要一个$O(26)$的哈希表来统计$s$中每个字母的频数。综上，整个算法的额外空间复杂度为$O(max(n,2600^2))$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
const int N = 50005;
char s[N];
int n, used[N];
vector<int> pos[26];
unordered_map<int, int> dp[N];

int dfs(int l, int r) {
    if(l > r) return dp[l][r] = 0;
    if(l == r) return dp[l][r] = 1;
    if(dp[l].count(r)) return dp[l][r];
    // 抛弃s[l]
    int res = dfs(l + 1, r);
    // 找一个最右的s[l]与其匹配
    int k = s[l] - 'a';
    auto it = upper_bound(pos[k].begin(), pos[k].end(), r);
    if(it != pos[k].begin()) {
        --it;
        int index = *it;
        if(index > l) {
            res = max(res, 2 + dfs(l + 1, index - 1));
        }
    }
    return dp[l][r] = res;
}

void dfs(int l, int r, int rest) {
    if(l > r || rest == 0) return;
    if(l == r) {
        used[l] = 1;
        return;
    }
    if(dp[l + 1].count(r) && dp[l + 1][r] == rest) {
        dfs(l + 1, r, rest);
    }else {
        int k = s[l] - 'a';
        auto it = upper_bound(pos[k].begin(), pos[k].end(), r);
        if(it != pos[k].begin()) {
            --it;
            int index = *it;
            if(index > l) {
                used[l] = used[index] = 1;
                dfs(l + 1, index - 1, rest - 2);
            }
        }
    }
}

int main() {
    scanf("%s", s + 1);
    n = strlen(s + 1);
    if(n >= 2600) {
        unordered_map<char, int> counter;
        char c;
        int maxfreq = 0;
        for(int i = 1; i <= n; i++) {
            counter[s[i]]++;
            if(counter[s[i]] >= maxfreq) {
                maxfreq = counter[s[i]];
                c = s[i];
            }
        }
        string ans(min(maxfreq, 100), c);
        cout << ans << endl;
    }else {
        for(int i = 1; i <= n; i++) {
            dp[i].clear();
            used[i] = 0;
        }
        for(int i = 0; i < 26; i++) {
            pos[i].clear();
        }
        for(int i = 1; i <= n; i++) {
            pos[s[i] - 'a'].push_back(i);
        }
        int maxlen = dfs(1, n);
        dfs(1, n, maxlen);
        string ans;
        for(int i = 1; i <= n; i++) {
            if(used[i]) ans.push_back(s[i]);
        }
        if(ans.size() < 100) {
            cout << ans << endl;
        }else {
            int sz = ans.size();
            if(sz&1) {
                int mid = sz>>1;
                string left = ans.substr(0, mid);
                string right = ans.substr(mid + 1);
                cout << left.substr(left.size() - 50) << right.substr(0, 50);
            }else {
                int rest = sz - 100 >> 1;
                cout << ans.substr(rest, 100) << endl;
            }
        }
    }
    return 0;
}