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

1
from math import gcd
2

3

4
class Solution:
5
    def makeStringSorted(self, s: str) -> int:
6
        s = [ord(c) - ord("a") for c in s]
7
        ans, MOD = 0, 10**9 + 7
8
        cnt, t, d, step = [0] * 26, 1, 1, 1
9
        cnt[s[-1]] = 1
10
        for c in reversed(s[:-1]):
11
            d *= cnt[c] + 1
12
            t *= step
13
            g = gcd(d, t)
14
            d //= g
15
            t //= g
16
            ans = (ans + t * sum(cnt[i] for i in range(c)) // d) % MOD
17
            cnt[c] += 1
18
            step += 1
19
        return ans