Inversion Count
Inversion count works\n\nCreate a frequency map for each digit in t.\n\n        n = len(s)\n        for i in range(n - 1, -1, -1):\n            prev = int(t[i +
**Inversion count works**\n\nCreate a frequency map for each digit in t.\n```\n        n = len(s)\n        for i in range(n - 1, -1, -1):\n            prev = int(t[i + 1]) if i + 1 < n else None \n            c = int(t[i])\n            \n            f = [0]*10 if prev not in mem else mem[prev][-1][::]\n            f[c] += 1\n            \n            if c not in mem:\n                mem[c] = []\n            \n            mem[c].append(f)\n```\n\nNow we will iterate through s and see if the inversions in s exceed for every possibility the inversions in t.\n```\n        curr = [0] * 10\n        for i in range(n - 1, -1, -1):\n            c = int(s[i])\n            curr[c] += 1\n            if c not in mem:\n                return False\n            \n            target = mem[c].pop()\n            if len(mem[c]) == 0:\n                del mem[c]\n\n            #check values larger than c and make sure you have enough\n            for x in range(0, c):\n                if curr[x] < target[x]:\n                    return False\n```\nProof:\nSay we start at the first digit of t, call it `t_0`. \n1. Get the first time `t_0` occurs in s call this index `i0`\n2. Compare their inversions. If `t_0` has more inversions with say `a` (s.t `a > t_0 where a has its index after t_0`) than found for `t_0` in s, then that would imply there exists at least one `a` to the right of `t_0` in t that is not in s. Since sorting operation can\'t create this extra inversion we can return false.\n3. A less trivial case is when s has at least as many inversions as t does for the first time `t_0` occurs.\n\t1. Case 1: `i0` is 0, then no work has to occur since the first time `t_0` occurs is at index 0 for both s and t.\n\t2. Case 2: `i0` > 0. If `min(s[:i0 + 1]) == t_0` then we can move `t_0` to the front of s.\n\t3. Case 3: `i0` > 0 but there exists a value `x` s.t `x < t_0 and index(x) < i0`. Say that t had `n` inversions for the first `t_0` of the type `(t_0, x)`. That means that `x_0` in s also had at least `n` inversions say `n\'`. It\'s very important to know that each frequency in s and t for each letter must be identical otherwise you won\'t have enough digits of s to form t in any way. Since we know that t had `n` inversions, then there are exactly `n` `x\'s that exist for both t and s` which means that `x_0` is *followed* by exactly `n` instances of `x` in s, but we assumed that there is another one *before* `x_0` which is a contradiction. Hence, this case can\'t happen.\n4. Once you processed the first digit for both s and t, go to step 1 but with t = t[1:] and s with index 0 being swapped with `i0` and then s = s[1:]\n\nFull code\n```\ndef isTransformable(self, s: str, t: str) -> bool:\n        if len(s) != len(t):\n            return False\n        \n        mem = {}\n        \n        n = len(s)\n        for i in range(n - 1, -1, -1):\n            prev = int(t[i + 1]) if i + 1 < n else None \n            c = int(t[i])\n            \n            f = [0]*10 if prev not in mem else mem[prev][-1][::]\n            f[c] += 1\n            \n            if c not in mem:\n                mem[c] = []\n            \n            mem[c].append(f)\n        for key in mem:\n            mem[key] = mem[key][::-1]\n \n\n        curr = [0] * 10\n        for i in range(n - 1, -1, -1):\n            c = int(s[i])\n            \n            curr[c] += 1\n            \n            if c not in mem:\n                return False\n            \n            target = mem[c].pop()\n            if len(mem[c]) == 0:\n                del mem[c]\n\n            #check values larger than c and make sure you have enough\n            for x in range(0, c):\n                if curr[x] < target[x]:\n                    return False\n        return True\n```\nRuntime, O(n), space O(n)\n
[]