BEAUTYSTR - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: jubhai
Tester: mexomerf
Editorialist: raysh07

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

There is a string s, and we must find the number of beautiful non-empty strings y. The conditions for beauty are:

  1. f(c, y) \le f(c, s) for all characters c, where f(c, x) counts the frequency of c in x.
  2. y is lexicographically smallest string among all possible rearrangements of the characters in y

EXPLANATION:

Suppose we fix the multiset of characters that we will use. Then, due to the lexicographically minimal condition, there is exactly one string y which is beautiful, and that is the one where all the characters are sorted.

Thus, the problem reduces to counting the number of multisets of characters such that frequency of a character c \le f(c, s).

Note that here all the characters are independent of each other, and thus the frequency of a specific character c can be any of 0, 1, …, f(c, s), i.e. there are f(c, s) + 1 choices for the frequency of a character c, independently of the choices for the frequencies of other characters. Hence, the number of multisets is simply (f('a', s) + 1) \cdot (f('b', s) + 1) \cdot ..... \cdot (f('z', s) + 1).

However, there is a small case when we choose all characters to have frequency 0 in the multiset, which leads us to an empty string, which is not allowed as per the problem. Thus, we have to subtract 1 from our answer, and the final expression is (f('a', s) + 1) \cdot (f('b', s) + 1) \cdot ..... \cdot (f('z', s) + 1) - 1.

All f(c, s) can be computed in \mathcal{O}(n) by using a frequency array.

TIME COMPLEXITY:

\mathcal{O}(n + A) per testcase, where A = 26 is alphabet size.

CODE:

Editorialist's Code (C++) 
#include <bits/stdc++.h>
using namespace std;

int main(){
    int t; cin >> t;
    while (t--){
        int n; cin >> n;
        string s; cin >> s;
        const int mod = 1e9 + 7;
        int ans = 1;
        vector <int> f(26, 0);
        for (int i = 0; i < n; i++){
            f[s[i] - 'a']++;
        }
        
        for (int i = 0; i < 26; i++) ans = 1LL * ans * (f[i] + 1) % mod;
        ans--;
        if (ans < 0) ans += mod;
        
        cout << ans << "\n";
    }
    return 0;
}
3 Likes