Minimum Number of Operations to Make String Sorted

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution:
    @lru_cache(None)
    def f(self,i):
        return 1 if i <= 1 else (self.f(i-1)*i) % (10**9+7)

    @lru_cache(None)
    def inv(self, i):
        N = 10**9 + 7
        return pow(i, N-2, N)

    def makeStringSorted(self, s):
        N, n, out = 10**9 + 7, len(s), 0
        cnt = [0]*26
        for i in range(n-1, -1, -1):
            ind = ord(s[i]) - ord("a")
            cnt[ind] += 1
            ans = sum(cnt[:ind]) * self.f(n-i-1)
            for j in range(26):
                ans = ans * self.inv(self.f(cnt[j])) % N
            out += ans
        return out % N