子序列的个数

求一个字符串中子序列出现的个数，如QQQ

Acwing 4082

暴力

枚举QQQ所有可能出现的位置，时间复杂度为$O(n^3)$，空间复杂度为$O(1)$

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        char[] s = sc.next().toCharArray();
        int res = 0;
        for (int i = 0; i < s.length; i++) {
            for (int j = i + 1; j < s.length; j++) {
                for (int k = j + 1; k < s.length; k++) {
                    if (s[i] == 'Q' && s[j] == 'Q' && s[k] =='Q') 
                        res++;
                }
            }
        }
        System.out.println(res);
    }
}

前缀和

前缀和优化，时间复杂度为$O(3n)$，空间复杂度为$O(3n)$

求QQQ的子序列的个数，则可以等价于对于出现Q的位置i，[1, i)所有QQ出现的个数的和（以当前字母Q结尾的QQQ子序列个数）

注意是[1, i) = [1, i - 1]，因为是对于位置i之前出现的个数统计，否则使用[1, i]会统计重复的子序列

因此需要轮询对于[1, i)内QQ的个数，因此可以维护对于QQ出现次数的前缀和

同样可以转化为求解对于字母Q的前缀和

由于每次轮询都是[1, i)，因此返回的结果为$S_{i-1}-S_0 = S_{i-1}$，在实现时省略了-0

import java.util.*;

class Main {
    static final int N = 110;
    static int[] q = new int[N]; // Q的前缀和
    static int[] a = new int[N]; // QA的前缀和
    static int[] sum = new int[N]; // QAQ的前缀和
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        char[] s = (" " + sc.next()).toCharArray();
        for (int i = 1; i <s.length; i++) 
            if (s[i] == 'Q') 
                q[i] = q[i - 1] + 1;
            else
                q[i] = q[i - 1];
        for (int i = 1; i < s.length; i++) 
            if (s[i] == 'Q') 
                a[i] = a[i - 1] + q[i - 1];
            else
                a[i] = a[i - 1];
        for (int i = 1; i < s.length; i++)
            if (s[i] == 'Q')
                sum[i] = sum[i - 1] + a[i - 1];
            else 
                sum[i] = sum[i - 1];
        System.out.println(sum[s.length - 1]);
    }
}

优化前缀和

在扫描时统计前缀和，时间复杂度为$O(n)$，空间复杂度为$O(1)$

时间复杂度优化

观察可以在构造前缀和$S_i$时,只需要询问子序列的前缀和$S’_{i-1}$

因此可以通过一遍扫描来构造所有的前缀和

 for (int i = 1; i <s.length; i++) {
    q[i] = q[i - 1];
    if (s[i] == 'Q') q[i] += 1;
    a[i] = a[i - 1];
    if (s[i] == 'Q') a[i] += q[i - 1];
    sum[i] = sum[i - 1];
    if (s[i] == 'Q') sum[i] += a[i - 1];
}

空间复杂度优化

进一步观察发现在一遍扫描时，对于第i项前缀和，只需要询问$S’_{i-1}$，因此可以直接使用变量维护即可，而不需要使用数组维护[1, n]的所有前缀和

int q = 0, a = 0, sum = 0;
for (int i = 1; i <s.length; i++) {
    if (s[i] == 'Q') sum += a;
    if (s[i] == 'Q') a += q;
    if (s[i] == 'Q') q++;
}

注意在实现时，由于对第i项值会进行更新，而询问的是第i-1项，因此需要先询问再更新，所以变量的更新顺序与前面的代码的顺序相反

所有长度$\leq 2$的子序列的最大值

由于字符的个数是有限的，即26个，因此遍历所有可能的组合，对每种组合求子序列即可，时间复杂度为$O(26 \times 26 \times n)$

而在扫描过程中，仅仅对于一种字符组合进行处理。

因此可以使用空间换时间的方式，将每种组合的结果存下，优化成一次扫描，而对每种字符都进行处理。时间复杂度为$O(26n)$

import java.util.*;

class Main {
    static final int N = 26;
    static long[] s1 = new long[N]; // 子序列i的出现个数为s1[i-'a']
    static long[][] s2 = new long[N][N]; // 子序列ij的出现个数为s2[i-'a'][j-'a']
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        char[] s = sc.next().toCharArray();
        long res = 0;
        for (int i = 0; i < s.length; i++) {
            int c = s[i] - 'a';
            for (int j = 0; j < 26; j++) { // 所有以j开始c结尾子序列
                s2[j][c] += s1[j];
                res = Long.max(res, s2[j][c]);
            }
            s1[c]++;
            res = Long.max(res, s1[c]);
        }
        System.out.println(res);
    }
}

Acwing 3729