Skip to content

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

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
class Solution {
 public:
  int countKSubsequencesWithMaxBeauty(string s, int k) {
    unordered_map<char, int> count;
    for (const char c : s)
      ++count[c];
    if (count.size() < k)
      return 0;

    long ans = 1;

    for (const auto& [fc, numOfChars] : getFreqCountPairs(count)) {
      if (numOfChars >= k) {
        ans *= nCk(numOfChars, k) * modPow(fc, k);
        return ans % kMod;
      }
      ans *= modPow(fc, numOfChars);
      ans %= kMod;
      k -= numOfChars;
    }

    return ans;
  }

 private:
  static constexpr int kMod = 1'000'000'007;

  vector<pair<int, int>> getFreqCountPairs(
      const unordered_map<char, int>& count) {
    unordered_map<int, int> freqCount;
    for (const auto& [_, value] : count)
      freqCount[value]++;
    vector<pair<int, int>> freqCountPairs;
    for (const auto& [fc, numOfChars] : freqCount)
      freqCountPairs.emplace_back(fc, numOfChars);
    sort(freqCountPairs.begin(), freqCountPairs.end(),
         [](const pair<int, int>& a, const pair<int, int>& b) {
      return b.first < a.first;
    });
    return freqCountPairs;
  }

  long nCk(int n, int k) {
    long res = 1;
    for (int i = 1; i <= k; ++i)
      res = res * (n - i + 1) / i;
    return res;
  }

  // Returns x^n % kMod
  int modPow(long x, long n) {
    if (n == 0)
      return 1;
    if (n & 1)
      return x * modPow(x % kMod, (n - 1)) % kMod;
    return modPow(x * x % kMod, (n / 2)) % kMod;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
public class Solution {
  public int countKSubsequencesWithMaxBeauty(String s, int k) {
    Map<Character, Integer> count = new HashMap<>();
    for (final char c : s.toCharArray())
      count.merge(c, 1, Integer::sum);
    if (count.size() < k)
      return 0;

    long ans = 1;

    for (Pair<Integer, Integer> pair : getFreqCountPairs(count)) {
      final int fc = pair.getKey();
      final int numOfChars = pair.getValue();
      if (numOfChars >= k) {
        ans *= nCk(numOfChars, k) * modPow(fc, k);
        return (int) (ans % kMod);
      }
      ans *= modPow(fc, numOfChars);
      ans %= kMod;
      k -= numOfChars;
    }

    return (int) ans;
  }

  private static final int kMod = 1_000_000_007;

  private List<Pair<Integer, Integer>> getFreqCountPairs(Map<Character, Integer> count) {
    // freqCount := (f(c), # of chars with f(c))
    Map<Integer, Integer> freqCount = new HashMap<>();
    for (final int value : count.values())
      freqCount.merge(value, 1, Integer::sum);
    List<Pair<Integer, Integer>> freqCountPairs = new ArrayList<>();
    for (Map.Entry<Integer, Integer> entry : freqCount.entrySet())
      freqCountPairs.add(new Pair<>(entry.getKey(), entry.getValue()));
    freqCountPairs.sort((a, b) -> b.getKey() - a.getKey());
    return freqCountPairs;
  }

  private long nCk(int n, int k) {
    long res = 1;
    for (int i = 1; i <= k; ++i)
      res = res * (n - i + 1) / i;
    return res;
  }

  // Returns x^n % kMod.
  private int modPow(long x, long n) {
    if (n == 0)
      return 1;
    if (n % 2 == 1)
      return (int) (x * modPow(x % kMod, (n - 1)) % kMod);
    return modPow(x * x % kMod, (n / 2)) % kMod;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
  def countKSubsequencesWithMaxBeauty(self, s: str, k: int) -> int:
    kMod = 1_000_000_007
    count = collections.Counter(s)
    if len(count) < k:
      return 0

    ans = 1
    # freqCount := (f(c), # of chars with f(c))
    freqCount = collections.Counter(count.values())

    for fc, numOfChars in list(sorted(freqCount.items(), reverse=True)):
      if numOfChars >= k:
        ans *= math.comb(numOfChars, k) * pow(fc, k, kMod)
        return ans % kMod
      ans *= pow(fc, numOfChars, kMod)
      ans %= kMod
      k -= numOfChars