[Python/Golang] We cannot create inversions
Idea\nAll we can do is to sort a subarray, namely, remove the inversions within a subarray. We never create new inversions. Thus the idea is to ensure the origi
**Idea**\nAll we can do is to sort a subarray, namely, remove the inversions within a subarray. We never create new inversions. Thus the idea is to ensure the original string contains **no less inversions** than the target string, for every possible inversion pair. Since there are only 10 different elements, we can use **bucket sort** instead of O(nlogn) methods.\n\nExample, \n- "12345", "12435"\n    - the original has count(inversion 4 => 3) = 0\n    - the target string has count(inversion 4 => 3) = 1 > 0, thus we are lacking inversion here. Impossible transformation.\n\n**Complexity**\n- Time: O(n)\n- Space: O(1)\n\n**Python 3**\n```\nclass Solution:\n    def isTransformable(self, s: str, t: str) -> bool:\n        if collections.Counter(s) != collections.Counter(t): return False\n        s = [*map(int, s)]\n        t = [*map(int, t)]\n        n = len(s)\n        \n        def get_invs(arr):\n            inversions = [[0] * 10 for _ in range(10)]\n            explored = [0] * 10\n            for a in arr:\n                for i in range(a + 1, 10):\n                    inversions[i][a] += explored[i]\n                explored[a] += 1                    \n            return inversions\n        \n        s_invs = get_invs(s)\n        t_invs = get_invs(t)\n        return all(se >= te for sl, tl in zip(s_invs, t_invs) for se, te in zip(sl, tl))\n```\n\n**Golang**\n```\nfunc isTransformable(s string, t string) bool {\n    if counter(s) != counter(t) { return false }\n    s_invs := getInvs(s)\n    t_invs := getInvs(t)\n    for i := range s_invs {\n        for j := range s_invs {\n            if s_invs[i][j] < t_invs[i][j] { return false }\n        }\n    }\n    return true\n}\n\nfunc counter(s string) [10]int {\n    res := [10]int{}\n    for _, c := range s {\n        res[c - \'0\']++\n    }\n    return res\n}\n\nfunc getInvs(s string) [][]int {\n    inversions := make([][]int, 10)\n    for i := range inversions {\n        inversions[i] = make([]int, 10)\n    }\n    explored := make([]int, 10)\n    for _, c := range s {\n        num := c - \'0\'\n        for i := num + 1; i < 10; i++ {\n            inversions[num][i] += explored[i]\n        }\n        explored[num]++\n    }\n    return inversions\n}\n```
[]