[Python] 15 line of code, straightforward O(n) using deque explained
The idea is that you loop through t\'s elements, and make sure that you can always get that element to the ith position by sort a subarray of s[i:].\nFor exampl
The idea is that you loop through t\'s elements, and make sure that you can always get that element to the ith position by sort a subarray of s[i:].\nFor example:\ns = 34521\nt = 23415\nstep 1: get 2 to the 1st position:\n\ts = (3452)1 -> 23451\nstep 2: get 3 to the 2nd position:\n\ts = 23451\nstep3: get 4 to the 3rd position:\n\ts =23451\nstep 4: get 1 to the 4th position:\n\ts = 234(51) -> 23415\nstep 5: get 5 to the 5th position:\n\ts = 23415\n\nSo the idea is that for each step, you go to s[i:] to find the position j s.t. s[j] == target element t[i] and make sure every s elements in s[i:j] is larger than your t[i]. Otherwise you won\'t be able to get that element to the front.\nFor example, s = \'23415\', it is impossible to move 5 to the front as there is 1 that smaller than 5 before it.\n\nThe O(n^2) version of the code is:\n```\nimport heapq\nclass Solution:\n    def isTransformable(self, s: str, t: str) -> bool:\n        s_char, t_char = self.countChar(s), self.countChar(t)\n        if sorted(s_char.items()) != sorted(t_char.items()): return False \n        n = len(s)\n        i, j = 0, n-1\n        while i < n and s[i] == t[i]:\n            i += 1 \n        while j >= i and s[j] == t[j]:\n            j -=1\n        if j-i+1 ==0: return True \n        s, t = [char for char in s[i:j+1]], [char for char in t[i:j+1]]\n        j = 0\n        n = len(t)\n        heap = []\n        for i, num in enumerate(t):\n            for j in range(n):\n                if s[j] == \'\': continue\n                if s[j] < num: return False\n                if s[j] == num:\n                    s[j] = \'\'\n                    break\n        return True \n            \n    def countChar(self, s):\n        res = {}\n        for char in s:\n            res[char] = res.get(char, 0) + 1\n        return res \n```\n\nAnd @LarryNY got smarter implementation using deque, with Time Complexity O(n):\n```\n    def isTransformable(self, s: str, t: str) -> bool:\n        N = len(s)\n        arr = [collections.deque() for _ in range(10)]\n        \n        for index, x in enumerate(s):\n            arr[int(x)].append(index)\n            \n        for x in t:\n            x = int(x)\n            \n            if len(arr[x]) == 0:\n                return False\n            \n            for j in range(x):\n                if len(arr[j]) > 0 and arr[j][0] < arr[x][0]:\n                    return False\n            arr[x].popleft()\n        \n        return True\n```\nI think his/her code explains itself already.\n\n
[]