Count K-Subsequences of a String with Maximum Beauty Solution || Leetcode Bi-Weekly 112

         

Count K-Subsequences of a String with Maximum Beauty 

Leetcode Bi-Weekly 112

Problem Link : https://leetcode.com/problems/count-k-subsequences-of-a-string-with-maximum-beauty/

Solution :

class Solution

{

public:

    int M = 1000000007;

    long long power(unsigned long long x, int y, int p)

    {

        unsigned long long res = 1;

        x = x % p;

        while (y > 0)

        {

            if (y & 1)

                res = (res * x) % p;

            y = y >> 1;

            x = (x * x) % p;

        }

        return res;

    }

    long long modInverse(long long n, int p)

    {

        return power(n, p - 2, p);

    }

    unsigned long long mul(long long x, long long y, int p)

    {

        return x * 1ll * y % p;

    }

    long long divide(long long x, long long y, int p)

    {

        return mul(x, modInverse(y, p), p);

    }

    long long ncrModM(long long n, int r, int p)

    {

        if (n < r)

            return 0;

        if (r == 0)

            return 1;

        if (n - r < r)

            return ncrModM(n, n - r, p);

        unsigned long long res = 1;

        for (int i = r; i >= 1; i--)

            res = divide(mul(res, n - i + 1, p), i, p);

        return res;

    }

    long long calculate(int n, int r, int freq)

    {

        long long ans = ncrModM(n, r, M);

        for (int i = 0; i < r; i++)

        {

            ans *= freq;

            ans %= M;

        }

        return (ans % M);

    }

    int countKSubsequencesWithMaxBeauty(string s, int k)

    {

        vector<int> a(26, 0);

        int unique = 0;

        for (auto i : s)

        {

            if (a[i - 'a'] == 0)

                unique++;

            a[i - 'a']++;

        }

        if (unique < k)

            return 0;

        priority_queue<int> pq;

        for (int i = 0; i < 26; i++)

        {

            if (a[i])

                pq.push(a[i]);

        }

        map<int, int> mp;

        for (int i = 0; i < k; i++)

        {

            mp[pq.top()]++;

            pq.pop();

        }

        long long ans = 1;

        for (auto i : mp)

        {

            int freq = i.first;

            int used = i.second;

            int temp = 0;

            for (int i = 0; i < 26; i++)

            {

                if (a[i] == freq)

                    temp++;

            }

            ans *= calculate(temp, used, freq);

            ans %= M;

        }

        return (int)ans;

    }

};