Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2539.html

2539. Count the Number of Good Subsequences

Description

A subsequence of a string is good if it is not empty and the frequency of each one of its characters is the same.

Given a string s, return the number of good subsequences of s. Since the answer may be too large, return it modulo 109 + 7.

A subsequence is a string that can be derived from another string by deleting some or no characters without changing the order of the remaining characters.

 

Example 1:

Input: s = "aabb"
Output: 11
Explanation: The total number of subsequences is 24. There are five subsequences which are not good: "aabb", "aabb", "aabb", "aabb", and the empty subsequence. Hence, the number of good subsequences is 24-5 = 11.

Example 2:

Input: s = "leet"
Output: 12
Explanation: There are four subsequences which are not good: "leet", "leet", "leet", and the empty subsequence. Hence, the number of good subsequences is 24-4 = 12.

Example 3:

Input: s = "abcd"
Output: 15
Explanation: All of the non-empty subsequences are good subsequences. Hence, the number of good subsequences is 24-1 = 15.

 

Constraints:

  • 1 <= s.length <= 104
  • s consists of only lowercase English letters.

Solutions

  • 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;
        }
    }
    
  • 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
    
    
  • 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
    }
    
    func max(a, b int) int {
    	if a > b {
    		return a
    	}
    	return b
    }
    

All Problems

All Solutions