Skip to content

Latest commit

 

History

History
279 lines (224 loc) · 7.23 KB

README.md

File metadata and controls

279 lines (224 loc) · 7.23 KB
comments difficulty edit_url tags
true
中等
哈希表
数学
字符串
组合数学
计数

2539. 好子序列的个数 🔒

English Version

题目描述

如果字符串的某个 子序列 不为空，且其中每一个字符出现的频率都相同，就认为该子序列是一个好子序列。

给你一个字符串 s ，请你统计并返回它的好子序列的个数。由于答案的值可能非常大，请返回对 109 + 7 取余的结果作为答案。

字符串的 子序列 是指，通过删除一些（也可以不删除）字符且不改变剩余字符相对位置所组成的新字符串。

 

示例 1：

输入：s = "aabb"
输出：11
解释：s 的子序列的总数为 24 = 16 。其中，有 5 个子序列不是好子序列，分别是 "aabb"，"aabb"，"aabb"，"aabb" 以及空字符串。因此，好子序列的个数为 16 - 5 = 11 。

示例 2：

输入：s = "leet"
输出：12
解释：s 的子序列的总数为 24 = 16 。其中，有 4 个子序列不是好子序列，分别是 "leet"，"leet"，"leet" 以及空字符串。因此，好子序列的个数为 16 - 4 = 12 。

示例 3：

输入：s = "abcd"
输出：15
解释：s 所有非空子序列均为好子序列。因此，好子序列的个数为 16 - 1 = 15 。

 

提示：

  • 1 <= s.length <= 104
  • s 仅由小写英文字母组成

解法

方法一：枚举 + 组合计数

由于题目说的是子序列中字母出现的次数，因此，我们可以先用一个数组 $cnt$ 统计字符串 $s$ 中每个字母出现的次数，记最大的次数为 $mx$。

接下来，我们在 $[1,2..mx]$ 范围内枚举子序列中字母出现的次数 $i$，然后枚举所有出现过的字母，如果该字母 $c$ 的出现次数 $cnt[c]$ 大于等于 $i$，那么我们可以从这 $cnt[c]$ 个相同字母中选择其中 $i$ 个，也可以一个都不选，那么当前字母的可选方案数就是 $comb(cnt[c], i) + 1$，将所有可选方案数相乘，可以得到当前次数的所有子序列次数，将次数减去 $1$ 累加到答案中。

那么问题的关键在于如何快速求出 $comb(n, k)$，我们可以用逆元来求解，具体实现见代码。

时间复杂度 $O(n \times C)$，空间复杂度 $O(n)$。其中 $n$ 为字符串 $s$ 的长度，而 $C$ 是字符集的大小，本题中 $C = 26$。

Python3

N = 10001
MOD = 10**9 + 7
f = [1] * N
g = [1] * N
for i in range(1, N):
    f[i] = f[i - 1] * i % MOD
    g[i] = pow(f[i], MOD - 2, MOD)


def comb(n, k):
    return f[n] * g[k] * g[n - k] % MOD


class Solution:
    def countGoodSubsequences(self, s: str) -> int:
        cnt = Counter(s)
        ans = 0
        for i in range(1, max(cnt.values()) + 1):
            x = 1
            for v in cnt.values():
                if v >= i:
                    x = x * (comb(v, i) + 1) % MOD
            ans = (ans + x - 1) % MOD
        return ans

Java

class Solution {
    private static final int N = 10001;
    private static final int MOD = (int) 1e9 + 7;
    private static final long[] F = new long[N];
    private static final long[] G = new long[N];

    static {
        F[0] = 1;
        G[0] = 1;
        for (int i = 1; i < N; ++i) {
            F[i] = F[i - 1] * i % MOD;
            G[i] = qmi(F[i], MOD - 2, MOD);
        }
    }

    public static long qmi(long a, long k, long p) {
        long res = 1;
        while (k != 0) {
            if ((k & 1) == 1) {
                res = res * a % p;
            }
            k >>= 1;
            a = a * a % p;
        }
        return res;
    }

    public static long comb(int n, int k) {
        return (F[n] * G[k] % MOD) * G[n - k] % MOD;
    }

    public int countGoodSubsequences(String s) {
        int[] cnt = new int[26];
        int mx = 1;
        for (int i = 0; i < s.length(); ++i) {
            mx = Math.max(mx, ++cnt[s.charAt(i) - 'a']);
        }
        long ans = 0;
        for (int i = 1; i <= mx; ++i) {
            long x = 1;
            for (int j = 0; j < 26; ++j) {
                if (cnt[j] >= i) {
                    x = x * (comb(cnt[j], i) + 1) % MOD;
                }
            }
            ans = (ans + x - 1) % MOD;
        }
        return (int) ans;
    }
}

C++

int N = 10001;
int MOD = 1e9 + 7;
long f[10001];
long g[10001];

long qmi(long a, long k, long p) {
    long res = 1;
    while (k != 0) {
        if ((k & 1) == 1) {
            res = res * a % p;
        }
        k >>= 1;
        a = a * a % p;
    }
    return res;
}

int init = []() {
    f[0] = 1;
    g[0] = 1;
    for (int i = 1; i < N; ++i) {
        f[i] = f[i - 1] * i % MOD;
        g[i] = qmi(f[i], MOD - 2, MOD);
    }
    return 0;
}();

int comb(int n, int k) {
    return (f[n] * g[k] % MOD) * g[n - k] % MOD;
}

class Solution {
public:
    int countGoodSubsequences(string s) {
        int cnt[26]{};
        int mx = 1;
        for (char& c : s) {
            mx = max(mx, ++cnt[c - 'a']);
        }
        long ans = 0;
        for (int i = 1; i <= mx; ++i) {
            long x = 1;
            for (int j = 0; j < 26; ++j) {
                if (cnt[j] >= i) {
                    x = (x * (comb(cnt[j], i) + 1)) % MOD;
                }
            }
            ans = (ans + x - 1) % MOD;
        }
        return ans;
    }
};

Go

const n = 1e4 + 1
const mod = 1e9 + 7

var f = make([]int, n)
var g = make([]int, n)

func qmi(a, k, p int) int {
	res := 1
	for k != 0 {
		if k&1 == 1 {
			res = res * a % p
		}
		k >>= 1
		a = a * a % p
	}
	return res
}

func init() {
	f[0], g[0] = 1, 1
	for i := 1; i < n; i++ {
		f[i] = f[i-1] * i % mod
		g[i] = qmi(f[i], mod-2, mod)
	}
}

func comb(n, k int) int {
	return (f[n] * g[k] % mod) * g[n-k] % mod
}

func countGoodSubsequences(s string) (ans int) {
	cnt := [26]int{}
	mx := 1
	for _, c := range s {
		cnt[c-'a']++
		mx = max(mx, cnt[c-'a'])
	}
	for i := 1; i <= mx; i++ {
		x := 1
		for _, v := range cnt {
			if v >= i {
				x = (x * (comb(v, i) + 1)) % mod
			}
		}
		ans = (ans + x - 1) % mod
	}
	return
}