Skip to content

1830. Minimum Number of Operations to Make String Sorted

  • Time: $O(26n) = 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
class Solution {
 public:
  int makeStringSorted(string s) {
    const int n = s.length();
    const auto [fact, invFact] = getFactAndInvFact(n);
    int ans = 0;
    vector<int> count(26);

    for (int i = n - 1; i >= 0; --i) {
      const int order = s[i] - 'a';
      ++count[order];
      long perm = accumulate(count.begin(), count.begin() + order, 0) *
                  fact[n - 1 - i] % kMod;
      for (int j = 0; j < 26; ++j)
        perm = perm * invFact[count[j]] % kMod;
      ans = (ans + perm) % kMod;
    }

    return ans;
  }

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

  pair<vector<long>, vector<long>> getFactAndInvFact(int n) {
    vector<long> fact(n + 1);
    vector<long> invFact(n + 1);
    vector<long> inv(n + 1);
    fact[0] = invFact[0] = 1;
    inv[0] = inv[1] = 1;
    for (int i = 1; i <= n; ++i) {
      if (i >= 2)
        inv[i] = kMod - kMod / i * inv[kMod % i] % kMod;
      fact[i] = fact[i - 1] * i % kMod;
      invFact[i] = invFact[i - 1] * inv[i] % kMod;
    }
    return {fact, invFact};
  }
};

 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
class Solution {
  public int makeStringSorted(String s) {
    final int kMod = 1_000_000_007;
    final int n = s.length();
    final long[][] factAndInvFact = getFactAndInvFact(n);
    final long[] fact = factAndInvFact[0];
    final long[] invFact = factAndInvFact[1];
    int ans = 0;
    int[] count = new int[26];

    for (int i = n - 1; i >= 0; --i) {
      final int order = s.charAt(i) - 'a';
      ++count[order];
      long perm = Arrays.stream(count, 0, order).sum() * fact[n - 1 - i] % kMod;
      for (int j = 0; j < 26; ++j)
        perm = perm * invFact[count[j]] % kMod;
      ans += perm;
      ans %= kMod;
    }

    return ans;
  }

  private static final int kMod = 1_000_000_007;

  private long[][] getFactAndInvFact(int n) {
    long[] fact = new long[n + 1];
    long[] invFact = new long[n + 1];
    long[] inv = new long[n + 1];
    fact[0] = invFact[0] = 1;
    inv[0] = inv[1] = 1;
    for (int i = 1; i <= n; ++i) {
      if (i >= 2)
        inv[i] = kMod - kMod / i * inv[kMod % i] % kMod;
      fact[i] = fact[i - 1] * i % kMod;
      invFact[i] = invFact[i - 1] * inv[i] % kMod;
    }
    return new long[][] {fact, invFact};
  }
}

 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
class Solution:
  def makeStringSorted(self, s: str) -> int:
    kMod = 1_000_000_007
    ans = 0
    count = [0] * 26

    @functools.lru_cache(None)
    def fact(i: int) -> int:
      return 1 if i <= 1 else i * fact(i - 1) % kMod

    @functools.lru_cache(None)
    def inv(i: int) -> int:
      return pow(i, kMod - 2, kMod)

    for i, c in enumerate(reversed(s)):
      order = string.ascii_lowercase.index(c)
      count[order] += 1
      # count[:order] := s[i] can be any character smaller than c
      # fact(i) := s[i + 1..n - 1] can be any sequence of characters
      perm = sum(count[:order]) * fact(i)
      for j in range(26):
        perm = perm * inv(fact(count[j])) % kMod
      ans = (ans + perm) % kMod

    return ans