Minimum Number of Operations to Make String Sorted LeetCode solution in Java

1
import java.math.*;
2

3
class Solution {
4
  public int makeStringSorted(String s) {
5
    BigInteger res = new BigInteger("0");
6
    BigInteger mod = new BigInteger("1000000007");
7

8
    int[] count = new int[26];
9
    BigInteger[] fact = factory(s.length(), mod);
10

11
    int n = s.length();
12
    BigInteger div = new BigInteger("1");
13

14
    for (int i = n - 1; i >= 0; --i) {
15
      char c = s.charAt(i);
16
      count[c - 'a']++;
17
      BigInteger c1 = countInverse(count, c);
18
      BigInteger ans = c1.multiply(fact[n - i - 1]);
19
      div = div.multiply(new BigInteger(String.valueOf(count[c - 'a'])));
20
      ans = ans.multiply(div.modPow(mod.subtract(new BigInteger(String.valueOf(2))), mod)).mod(mod);
21
      res = res.add(ans).mod(mod);
22
    }
23

24
    return res.intValue();
25
  }
26

27
  public BigInteger countInverse(int[] count, char c) {
28
    long cnt = 0;
29
    for (int i = 0; i < (c - 'a'); ++i) {
30
      cnt += count[i];
31
    }
32

33
    return new BigInteger(String.valueOf(cnt));
34
  }
35

36
  public BigInteger[] factory(int n, BigInteger mod) {
37
    BigInteger[] fact = new BigInteger[n + 1];
38
    fact[0] = new BigInteger("1");
39
    for (int i = 1; i <= n; ++i) {
40
      fact[i] = fact[i - 1].multiply(new BigInteger(String.valueOf(i))).mod(mod);
41
    }
42

43
    return fact;
44
  }
45
}