【Leetcode】1830. Minimum Number of Operations to Make String Sorted

题目地址：

https://leetcode.com/problems/minimum-number-of-operations-to-make-string-sorted/description/

给定一个长$n$字符串$s$，每次进行这样的操作：找到最大的$i$使得$s[i-1]>s[i]$，再找到最大的$j$使得$\forall k\in [i,j],s[i-1]>s[k]$，交换$s[i-1],s[j]$并翻转$s[i:]$。问进行多少次操作可以使得$s$变为升序。答案模$10^9+7$返回。题目保证$s$只含英文小写字母。

这个操作实际上就是求字典序比$s$小的最大排列，参考https://blog.csdn.net/qq_46105170/article/details/108543529。那么要求$s$进行多少次操作就能升序，即问$s$进行多少次操作其字典序会变为最小，即问$s$按字典序排名是多少（排名从$0$开始）。求某个排列的字典序排名可以用康托展开，思路和算法参考https://blog.csdn.net/qq_46105170/article/details/127711927。本题还需要求模$10^9+7$的逆元，可以用费马小定理和快速幂来做，参考https://blog.csdn.net/qq_46105170/article/details/113823892。代码如下：

class Solution {
 public:
  vector<int> tr;
  int n;
#define lowbit(x) (x & -x)

  void add(int k, int x) {
    for (; k <= n; k += lowbit(k)) tr[k] += x;
  }

  int sum(int k) {
    int res = 0;
    for (; k; k -= lowbit(k)) res += tr[k];
    return res;
  }

  int makeStringSorted(string s) {
    const int P = 1e9 + 7;
    n = *max_element(s.begin(), s.end()) - 'a' + 1;
    tr.resize(n + 1);
    auto fast_pow = [&](long x, int pow = P - 2) {
      long res = 1;
      while (pow) {
        if (pow & 1) res = res % P * x % P;
        pow >>= 1;
        x = x % P * x % P;
      }

      return res;
    };

    long res = 0, fact = 1, mult = 1;
    int cnt[27];
    memset(cnt, 0, sizeof cnt);
    for (int i = s.size() - 1; i >= 0; i--) {
      int x = s[i] - 'a' + 1;
      cnt[x]++;
      mult = mult * fast_pow(cnt[x]) % P;
      add(x, 1);
      res = (res + fact * mult % P * sum(x - 1)) % P;
      fact = (s.size() - i) * fact % P;
    }

    return res;
  }
};
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

时空复杂度$O(n)$（树状数组上的操作可以视为常数时间，因为树状数组长度不超过$27$）。

也可以直接用https://blog.csdn.net/qq_46105170/article/details/127711927里的公式暴力求，代码如下：

class Solution {
 public:
  int makeStringSorted(string s) {
    const int P = 1e9 + 7;
    int n = s.size();
    long f[n + 1], g[n + 1];
    f[0] = g[0] = 1;
    auto fast_pow = [&](long a, int b) {
      long res = 1;
      while (b) {
        if (b & 1) res = res * a % P;
        a = a * a % P;
        b >>= 1;
      }

      return res;
    };
    for (int i = 1; i <= n; i++) {
      f[i] = f[i - 1] * i % P;
      g[i] = fast_pow(f[i], P - 2);
    }

    int res = 0, cnt[26], sum = n;
    memset(cnt, 0, sizeof cnt);
    auto calc = [&](int sum) {
      int res = f[sum];
      for (int i = 0; i < 26; i++) res = (long)res * g[cnt[i]] % P;
      return res;
    };
    for (char ch : s) cnt[ch - 'a']++;
    for (int k = 0; k < s.size(); k++) {
      int x = s[k] - 'a';
      for (int i = 0; i < x; i++) {
        if (!cnt[i]) continue;
        cnt[i]--;
        res = (res + calc(n - 1 - k)) % P;
        cnt[i]++;
      }

      cnt[x]--;
    }

    return res;
  }
};
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

时空复杂度$O(n)$。