求本题思路，字符串？

Question

题目描述
小 C 班上的语文课代表。
他常常在作文里使用各种形如“ABAB”的四字词语。诸如“碧蓝碧蓝”“锻炼锻炼”“琢
磨琢磨”“彼此彼此”，都是他平日写作文时的最爱。
现在，他的眼前飘过了一串字符序列。他想知道其中会有多少个形如“ABAB”的子序列，
你能告诉他吗？
具体地，你会得到一个长度为 N 的字符序列 S。方便起见，我们用 0, 1, 2, . . . N − 1 为 S
中的每一位字符依次编号，并用 Si 表示 S 中编号为 i 的字符。e 你的任务是找出所有的整数
四元组 (i, j, k, l)，满足 0 ≤ i < j < k < l < N 且 Si = Sk, Sj = Sl , Si 不等于Sj。
输入格式
第一行为一个整数 N，表示字符序列的长度。
第二行为一个长度 N 的字符串，字符串仅包含大写字母，表示给定的字符序列。
输出格式
一个整数，表示给定的字符序列中有多少个形如“ABAB”的子序列。
答案可能很大，请输出对 109 + 7 取模之后的结果。
输入样例 复制
8
ABCBCACA
输出样例 复制
6

Answer 1

引自免费微信小程序-皆我百晓生，希望对题主有所帮助，如有帮助，还望采纳。

---

这道题目可以使用动态规划来解决。

首先，我们定义一个二维数组dp，其中dp[i][j]表示以字符序列S的第i个字符和第j个字符结尾的形如'ABAB'的子序列的个数。

然后，我们遍历字符序列S的每一个字符，假设当前字符为S[i]，我们再遍历之前的每一个字符S[j]，其中j < i。如果S[i]和S[j]相等，那么我们再遍历之前的每一个字符S[k]，其中k < j。如果S[k]和S[i]不相等，那么我们就找到了一个形如'ABAB'的子序列，此时dp[i][j]的值就应该加上dp[j][k]。

最后，我们遍历dp数组，将所有的dp[i][j]的值相加，就得到了形如'ABAB'的子序列的总个数。

最后，我们将结果对109 + 7取模，得到最终的答案。

具体的实现可以参考下面的C++代码：

#include <iostream>
#include <vector>
using namespace std;

const int MOD = 1e9 + 7;

int countABABSubsequences(int N, string S) {
    vector<vector<int>> dp(N, vector<int>(N, 0));
    int ans = 0;
    
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < i; j++) {
            if (S[i] == S[j]) {
                for (int k = 0; k < j; k++) {
                    if (S[k] != S[i]) {
                        dp[i][j] = (dp[i][j] + dp[j][k]) % MOD;
                    }
                }
            }
        }
    }
    
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < i; j++) {
            ans = (ans + dp[i][j]) % MOD;
        }
    }
    
    return ans;
}

int main() {
    int N;
    string S;
    cin >> N >> S;
    
    int ans = countABABSubsequences(N, S);
    cout << ans << endl;
    
    return 0;
}

希望对你有帮助！