What is the time complexity of LeetCode 2842. Count K-Subsequences of a String With Maximum Beauty?

The Python solution on this page runs in O(n).

What is the space complexity of LeetCode 2842. Count K-Subsequences of a String With Maximum Beauty?

The Python solution on this page uses O(|\Sigma|) auxiliary space.

Count K-Subsequences of a String With Maximum Beauty — LeetCode 2842 Python Solution

HardGreedyHash TableMathStringCombinatorics

Problem: #2842
Pattern: Greedy
Reading time: 3 min
Source: leetcode.com

The problem

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.

Example

Input: s = "bcca", k = 2
Output: 4
Explanation: From s we have f('a') = 1, f('b') = 1, and f('c') = 2.

Python solution

Python

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

Complexity

Measure	Complexity
Time	O(n)
Space	O(\|\Sigma\|) auxiliary

Pattern: Greedy

Take the locally best option every time — when you can prove that never costs you later. LeetCode 2842. Count K-Subsequences of a String With Maximum Beauty is filed here because LeetCode tags it Greedy, which is the vocabulary this hub collects.

The greedy guide has the Python template for the pattern and the 346 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 2842. Count K-Subsequences of a String With Maximum Beauty?: LeetCode 2842. Count K-Subsequences of a String With Maximum Beauty is rated Hard on LeetCode.
What is the time complexity of LeetCode 2842. Count K-Subsequences of a String With Maximum Beauty?: The Python solution on this page runs in O(n).
What is the space complexity of LeetCode 2842. Count K-Subsequences of a String With Maximum Beauty?: The Python solution on this page uses O(|\Sigma|) auxiliary space.
What topics does LeetCode 2842. Count K-Subsequences of a String With Maximum Beauty cover?: LeetCode 2842. Count K-Subsequences of a String With Maximum Beauty is tagged Greedy, Hash Table, Math, String and Combinatorics on LeetCode.