Minimum Number of Operations to Make String Sorted LeetCode solution in C++

1
const int MOD = 1e9 + 7;
2
const int N = 3010;
3

4
long f[N];
5
long g[N];
6

7
long qmi(long a, int k) {
8
  long res = 1;
9
  while (k != 0) {
10
    if ((k & 1) == 1) {
11
      res = res * a % MOD;
12
    }
13
    k >>= 1;
14
    a = a * a % MOD;
15
  }
16
  return res;
17
}
18

19
int init = []() {
20
  f[0] = g[0] = 1;
21
  for (int i = 1; i < N; ++i) {
22
    f[i] = f[i - 1] * i % MOD;
23
    g[i] = qmi(f[i], MOD - 2);
24
  }
25
  return 0;
26
}();
27

28
class Solution {
29
 public:
30
  int makeStringSorted(string s) {
31
    int cnt[26]{};
32
    for (char &c : s) {
33
      ++cnt[c - 'a'];
34
    }
35
    int n = s.size();
36
    long ans = 0;
37
    for (int i = 0; i < n; ++i) {
38
      int m = 0;
39
      for (int j = 0; j < 26; ++j) {
40
        if (j < s[i] - 'a') {
41
          m += cnt[j];
42
        }
43
      }
44
      long t = m * f[n - i - 1] % MOD;
45
      for (int j = 0; j < 26; ++j) {
46
        t = t * g[cnt[j]] % MOD;
47
      }
48
      ans = (ans + t) % MOD;
49
      --cnt[s[i] - 'a'];
50
    }
51
    return ans;
52
  }
53
};