Welcome to Subscribe On Youtube

2842. Count K-Subsequences of a String With Maximum Beauty

Description

You are given a string s and an integer k.

A k-subsequence is a subsequence of s, having length k, and all its characters are unique, i.e., every character occurs once.

Let f(c) denote the number of times the character c occurs in s.

The beauty of a k-subsequence is the sum of f(c) for every character c in the k-subsequence.

For example, consider s = "abbbdd" and k = 2:

  • f('a') = 1, f('b') = 3, f('d') = 2
  • Some k-subsequences of s are:
    • "abbbdd" -> "ab" having a beauty of f('a') + f('b') = 4
    • "abbbdd" -> "ad" having a beauty of f('a') + f('d') = 3
    • "abbbdd" -> "bd" having a beauty of f('b') + f('d') = 5

Return an integer denoting the number of k-subsequences whose beauty is the maximum among all k-subsequences. Since the answer may be too large, return it modulo 109 + 7.

A subsequence of a string is a new string formed from the original string by deleting some (possibly none) of the characters without disturbing the relative positions of the remaining characters.

Notes

  • f(c) is the number of times a character c occurs in s, not a k-subsequence.
  • Two k-subsequences are considered different if one is formed by an index that is not present in the other. So, two k-subsequences may form the same string.

 

Example 1:

Input: s = "bcca", k = 2
Output: 4
Explanation: From s we have f('a') = 1, f('b') = 1, and f('c') = 2.
The k-subsequences of s are: 
bcca having a beauty of f('b') + f('c') = 3 
bcca having a beauty of f('b') + f('c') = 3 
bcca having a beauty of f('b') + f('a') = 2 
bcca having a beauty of f('c') + f('a') = 3
bcca having a beauty of f('c') + f('a') = 3 
There are 4 k-subsequences that have the maximum beauty, 3. 
Hence, the answer is 4. 

Example 2:

Input: s = "abbcd", k = 4
Output: 2
Explanation: From s we have f('a') = 1, f('b') = 2, f('c') = 1, and f('d') = 1. 
The k-subsequences of s are: 
abbcd having a beauty of f('a') + f('b') + f('c') + f('d') = 5
abbcd having a beauty of f('a') + f('b') + f('c') + f('d') = 5 
There are 2 k-subsequences that have the maximum beauty, 5. 
Hence, the answer is 2. 

 

Constraints:

  • 1 <= s.length <= 2 * 105
  • 1 <= k <= s.length
  • s consists only of lowercase English letters.

Solutions

Solution 1: Greedy + Combinatorial Mathematics

First, we use a hash table $f$ to count the occurrence of each character in the string $s$, i.e., $f[c]$ represents the number of times character $c$ appears in the string $s$.

Since a $k$-subsequence is a subsequence of length $k$ in the string $s$ with unique characters, if the number of different characters in $f$ is less than $k$, then there is no $k$-subsequence, and we can directly return $0$.

Otherwise, to maximize the beauty value of the $k$-subsequence, we need to make characters with high beauty values appear as much as possible in the $k$-subsequence. Therefore, we can sort the values in $f$ in reverse order to get an array $vs$.

We denote the occurrence of the $k$th character in the array $vs$ as $val$, and there are $x$ characters with an occurrence of $val$.

Then we first find out the characters with occurrences greater than $val$, multiply the occurrences of each character to get the initial answer $ans$, and update the remaining number of characters to be selected to $k$. We need to select $k$ characters from $x$ characters, so the answer needs to be multiplied by the combination number $C_x^k$, and finally multiplied by $val^k$, i.e., $ans = ans \times C_x^k \times val^k$.

Note that we need to use fast power and modulo operations here.

The time complexity is $O(n)$, and the space complexity is $O( \Sigma )$. Here, $n$ is the length of the string, and $\Sigma$ is the character set. In this problem, the character set is lowercase letters, so $ \Sigma = 26$.
  • class Solution {
        public int countKSubsequencesWithMaxBeauty(String s, int k) {
            int[] f = new int[26];
            int n = s.length();
            int cnt = 0;
            for (int i = 0; i < n; ++i) {
                if (++f[s.charAt(i) - 'a'] == 1) {
                    ++cnt;
                }
            }
            if (cnt < k) {
                return 0;
            }
            Integer[] vs = new Integer[cnt];
            for (int i = 0, j = 0; i < 26; ++i) {
                if (f[i] > 0) {
                    vs[j++] = f[i];
                }
            }
            Arrays.sort(vs, (a, b) -> b - a);
            final int mod = (int) 1e9 + 7;
            long ans = 1;
            int val = vs[k - 1];
            int x = 0;
            for (int v : vs) {
                if (v == val) {
                    ++x;
                }
            }
            for (int v : vs) {
                if (v == val) {
                    break;
                }
                --k;
                ans = ans * v % mod;
            }
            int[][] c = new int[x + 1][x + 1];
            for (int i = 0; i <= x; ++i) {
                c[i][0] = 1;
                for (int j = 1; j <= i; ++j) {
                    c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;
                }
            }
            ans = ((ans * c[x][k]) % mod) * qmi(val, k, mod) % mod;
            return (int) ans;
        }
    
        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;
        }
    }
    
  • class Solution {
    public:
        int countKSubsequencesWithMaxBeauty(string s, int k) {
            int f[26]{};
            int cnt = 0;
            for (char& c : s) {
                if (++f[c - 'a'] == 1) {
                    ++cnt;
                }
            }
            if (cnt < k) {
                return 0;
            }
            vector<int> vs(cnt);
            for (int i = 0, j = 0; i < 26; ++i) {
                if (f[i]) {
                    vs[j++] = f[i];
                }
            }
            sort(vs.rbegin(), vs.rend());
            const int mod = 1e9 + 7;
            long long ans = 1;
            int val = vs[k - 1];
            int x = 0;
            for (int v : vs) {
                x += v == val;
            }
            for (int v : vs) {
                if (v == val) {
                    break;
                }
                --k;
                ans = ans * v % mod;
            }
            int c[x + 1][x + 1];
            memset(c, 0, sizeof(c));
            for (int i = 0; i <= x; ++i) {
                c[i][0] = 1;
                for (int j = 1; j <= i; ++j) {
                    c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
                }
            }
            ans = (ans * c[x][k] % mod) * qmi(val, k, mod) % mod;
            return ans;
        }
    
        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;
        }
    };
    
  • class Solution:
        def countKSubsequencesWithMaxBeauty(self, s: str, k: int) -> int:
            f = Counter(s)
            if len(f) < k:
                return 0
            mod = 10**9 + 7
            vs = sorted(f.values(), reverse=True)
            val = vs[k - 1]
            x = vs.count(val)
            ans = 1
            for v in vs:
                if v == val:
                    break
                k -= 1
                ans = ans * v % mod
            ans = ans * comb(x, k) * pow(val, k, mod) % mod
            return ans
    
    
  • func countKSubsequencesWithMaxBeauty(s string, k int) int {
    	f := [26]int{}
    	cnt := 0
    	for _, c := range s {
    		f[c-'a']++
    		if f[c-'a'] == 1 {
    			cnt++
    		}
    	}
    	if cnt < k {
    		return 0
    	}
    	vs := []int{}
    	for _, x := range f {
    		if x > 0 {
    			vs = append(vs, x)
    		}
    	}
    	sort.Slice(vs, func(i, j int) bool {
    		return vs[i] > vs[j]
    	})
    	const mod int = 1e9 + 7
    	ans := 1
    	val := vs[k-1]
    	x := 0
    	for _, v := range vs {
    		if v == val {
    			x++
    		}
    	}
    	for _, v := range vs {
    		if v == val {
    			break
    		}
    		k--
    		ans = ans * v % mod
    	}
    	c := make([][]int, x+1)
    	for i := range c {
    		c[i] = make([]int, x+1)
    		c[i][0] = 1
    		for j := 1; j <= i; j++ {
    			c[i][j] = (c[i-1][j-1] + c[i-1][j]) % mod
    		}
    	}
    	ans = (ans * c[x][k] % mod) * qmi(val, k, mod) % mod
    	return ans
    }
    
    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
    }
    
  • function countKSubsequencesWithMaxBeauty(s: string, k: number): number {
        const f: number[] = new Array(26).fill(0);
        let cnt = 0;
        for (const c of s) {
            const i = c.charCodeAt(0) - 97;
            if (++f[i] === 1) {
                ++cnt;
            }
        }
        if (cnt < k) {
            return 0;
        }
        const mod = 1e9 + 7;
        const vs: number[] = f.filter(v => v > 0).sort((a, b) => b - a);
        const val = vs[k - 1];
        const x = vs.filter(v => v === val).length;
        let ans = 1;
        for (const v of vs) {
            if (v === val) {
                break;
            }
            --k;
            ans = (ans * v) % mod;
        }
        const c: number[][] = new Array(x + 1).fill(0).map(() => new Array(k + 1).fill(0));
        for (let i = 0; i <= x; ++i) {
            c[i][0] = 1;
            for (let j = 1; j <= Math.min(i, k); ++j) {
                c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
            }
        }
        ans = (((ans * c[x][k]) % mod) * Number(qmi(BigInt(val), k, BigInt(mod)))) % mod;
        return ans;
    }
    
    function qmi(a: bigint, k: number, p: bigint): bigint {
        let res = 1n;
        while (k) {
            if ((k & 1) === 1) {
                res = (res * a) % p;
            }
            k >>= 1;
            a = (a * a) % p;
        }
        return res;
    }
    
    

All Problems

All Solutions