算法百度笔试（2021-9-7）子序列问题

@author：Jingdai
@date：2021.09.18

前几天做百度笔试的一个题没有a出来，今天有空，搜了大佬的题解，做了出来，现在总结一下。

题目描述

给你一个长度为 n 且全部由小写字母组成的字符串 s，问你有多少个子序列恰好包含 k 个字母？

输入描述，第一行两个整数 n 和 k，第二行输入一个长度为 n 的仅含小写字母的字符串 s。

输出描述，恰好包含k个字母的子序列的个数，由于个数可能会很大，所以输出对 1000000007 取余的结果。

示例输入1：

6 5
eecbad

示例输出1：

解释1：

显然有两个子序列"ecbad"满足要求，同时s自己也满足要求，因此答案为3

示例输入2：

10 2

示例输出2：

aaaccebecd

思路

我想估计很多人和我一样，首先想到的方法就是直接 dfs，对于字符串 s 的每个字母，都采取选和不选两种策略。在 dfs 的时候记录子序列的包含字母的个数，在叶子节点如果包含字母为 k，就使最后的结果加1。同时，当我们在 dfs 中如果我们发现当前包含的字母数已经超过 k 了，那么这个搜索树的子树已经不可能会是答案了，进行剪枝。最后写出的代码如下。


import java.util.*;

public class Main {

    private static int count = 0;

    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int n = s.nextInt();
        int k = s.nextInt();
        s.nextLine();
        char[] chars = s.nextLine().toCharArray();
        int[] memo = new int[26];

        dfs(chars, 0, n, 0, k, memo);

        System.out.println(count);
    }

    private static void dfs(char[] chars, int index, int n, int curSelect, int k, int[] memo) {
        if (curSelect > k) {
            // prune
            return;
        }

        if (index == n) {
            if (curSelect == k) {
                count++;
                count %= 1000000007;
            }
            return;
        }

        // dont select
        dfs(chars, index+1, n, curSelect, k, memo);

        // select
        int charIndex = chars[index] - 'a';
        memo[charIndex]++;
        if (memo[charIndex] == 1) {
            curSelect++;
        }
        dfs(chars, index+1, n, curSelect, k, memo);
        if (memo[charIndex] == 1) {
            curSelect--;
        }
        memo[charIndex]--;
    }

}

如果这么简单就拿下这个题我也不会再专门写一篇博客了。上面的方法在字符串 s 非常长时，就会出现栈递归的过深的问题，最后不能 ac，下面看一种更好的方法。思路参考牛客的一个大佬，链接在文末。

首先对于字符串 s，我们记录串 s 中每个字母出现的个数，比如 a 有 5 个，那么选择 a 有多少种方案呢？总共就有：

C51 + C52 + C53 + C54 + C55

上面C51代表组合数的意思，这里不好打上下标，大家懂就行。然后：

C51 + C52 + C53 + C54 + C55 = 2^5 - 1

所以如果k个字母中如果选了a，那么就一共有 2^5 - 1 种可能，同理，如果选b、c等等也可以算出对应的方案数，那不就可以将问题转换为在26个字母中选择 k 种，每种的方案数不同，一共的方案数有多少。这样就可以对每种字母进行 dfs，每次考虑选择这种字母和不选，在叶子节点进行判断是否选择了k种字母，这样最多也就会 dfs 26层，大大降低了递归的深度，最后的代码如下。


import java.util.*;

public class Main {

    private static int count = 0;

    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int n = s.nextInt();
        int k = s.nextInt();
        s.nextLine();
        char[] chars = s.nextLine().toCharArray();
        int[] charCount = new int[26];

        for (char c : chars) {
            charCount[c-'a']++;
        }
        int[] charComCount = new int[26];
        for (int i = 0; i < 26; i++) {
            if (charCount[i] != 0) {
                charComCount[i] = (int) Math.pow(2, charCount[i]) - 1;
            }
        }
        dfs(charComCount, 0, 0, k, 0);
        System.out.println(count);
    }

    private static void dfs(int[] charComCount, int index, int curSelect, int k, int curCount) {
        if (curSelect > k) {
            return;
        }

        while (index < 26 && charComCount[index] == 0) {
            index++;
        }

        if (index == 26) {
            if (curSelect == k) {
                count += curCount;
                count %= 1000000007;
            }
            return;
        }

        // dont select
        dfs(charComCount, index+1, curSelect, k, curCount);

        // select
        if (curCount == 0) {
            dfs(charComCount, index+1, curSelect+1, k, charComCount[index]);
        } else {
            dfs(charComCount, index+1, curSelect+1, k, curCount * charComCount[index]);
        }
    }
}