Python 3: TC O(N*log(U)) SC O(N+U): Check if there are Lower Chars in the Way, Segment Tree
Intuition\n\nThis is a tricky problem, it took me a long time to get the intution.\n\nEventually what I realized was\n we don\'t care about the number of operat
# Intuition\n\nThis is a tricky problem, it took me a long time to get the intution.\n\nEventually what I realized was\n* we don\'t care about the *number* of operations, we just care if it\'s possible\n* "possible" means we can do *any* number of operations\n* **the simplest operation is to sort two characters, i.e. swap a lower character to be before a higher character**\n\nSo the most primitive operation is e.g. `...21... -> ...12...`\n\nSorting any range of 3+ characters can be done with multiple of these operations. Why? Because **each primitive operation is one step of bubble sort.**\n\nSo another way to phrase the question is "is it possible for `t` to be some intermediate state of bubble-sorting `s`?" (for some potentially very weird order of swaps).\n\n## What Makes it Impossible?\n\n"That which is not forbidden is allowed."\n\nSo what makes this problem impossible? **It\'s impossible if `t` would force us to swap a later character in front of an earlier one.**\n\n## An Algorithm Takes Shape\n\nSuppose the next character/digit in `t` to match is `d`.\n* get the **next index of `d` that we haven\'t moved into position yet**, call it `k`\n* find the **minimum index of any lesser character `d\' < d` we haven\'t moved into place yet**, call it `l`\n  * this is `min_{d\' | d\' < d} (firstUnplaced(d\'))`\n* if `k < l` then we can swap the next copy of `c` in `s` into position with some number of swaps\n* if `k > l` then it\'s impossible: there\'s a lesser character `d\'` somewhere before `k`. That means we can\'t swap `d` below `l`. And therefore it\'s impossible.\n* if possible, **update the next index of `d` and any structure(s) involved in the min index of lesser characters**\n\nI **bolded** the operations we need to support quickly.\n\n# Approach\n\n## Finding the Min Index of Digit `d`\n\nTo quickly find the next, the classic solution is to\n* create a `deque` for each unique character\n* iterate through `i, c in enumerate(s)`, and append `i` to the deque for `c`\n\nThat gives us `O(1)` time access to the next index, and `O(1)` time `popleft` to find the next after we place each copy of `c`.\n\n## Finding the Min Index of Digits `d\' < d`\n\nFinding min/max/average/whatever over a *range* of values `lo..hi` is what I call a "range query."\n\nThere are four common ways in LC problems and interviews to do this, in order of how common they are:\n* brute force: scan over the `d\'` values and get the min\n* cumulative sums: if you don\'t need to update, then you can store the cumulative sum of elements in a vector (in-place update, or in a new array). Then the sum over `l..r` is `acc[r]-acc[l-1]` (or `-0` if `l==0`)\n  * but we *do* need to update; updating `acc` takes `O(U)` for `U` unique characters so we want something else\n* cumulative sums and other "subtractible aggregations:" *Fenwick tree*. The details of Fenwick trees are beyond the scope of this writeup, but look them up. They give `log(U)` time access to some aggregation for indices `0..u`. The left bound of the range for a Fenwick tree query is always `0`. To get `lo..hi`, you do `query(u) - query(lo-1)`.\n  * for technical reasons, updating a Fenwick tree is only `log` time if updating the parent node only involves the change to its child. In this case, changing the min does *not* have that property. That makes updating a Fenwick tree in this case very annoying, and probably strictly slower than brute force\n* **segment tree:** unlike Fenwick, we can query over `lo..hi`, *and* we can update *any* aggregation in `log(U)` time because each parent node only has two children\n  * the downside of segment trees is that they use 2x as much memory as Fenwick trees, are a bit slower, and a bit harder to code\n  * but if you memorize the implementation here, a segment tree is only slightly more annoying to write than a Fenwick tree\n\n## Updating Structures\n\n### Updating the Next Index of `d`\n\nThis one is easy with `deque`: `idxs[d].popleft()`. Ez!\n\nJust remember to check if the `deque` is empty, and if so, return some suitable dummy value like `len(s)`.\n\n### Updating the Segment Tree\n\nThis one is also "easy," in the sense that it\'s standard fare for a segment tree.\n\nThe algo is this:\n* update the next index for `d` in the tree, i.e. set that leaf\'s value in the segment tree\n* then while there is a parent:\n  * go to that parent\n  * update the aggregation: `parentMin = min(leftChildMin, rightChildMin)`\n\nAs an optimization, when the parent\'s aggregation stops changing, I exit immediately. The parent\'s ancestors are already consistent with the current parent\'s value so we can skip doing `log(U)` operations in the best case.\n\n# Complexity\n- Time complexity: `O(N*log(U))` for `N` chars in the strings and `U` unique characters. We get `log(U)` instead of `U` by querying a segment tree for the range min rather than brute-forcing it\n\n- Space complexity: `O(N + U)`\n  - `O(N)` for storing all the indices for all uniques\n  - `O(U)` for entries in the segment tree, and for the `O(1)` overhead per unique character in making a `idxs` entry and its `deque`\n\n# Speed in Practice\n\nThis solution, despite having better asymptotic complexity than the "brute force minimum" for `d\' < d`, is actually slower.\n\nThe reason is there are only 10 digits, so on average, brute force only needs to check 4-5 other digits for querying the minimum, and do `O(1)` work to update the next digit for `d`: just `popleft()` on its deque. So on average we have ~6 operations.\n\nMeanwhile, the segment trees\n* need to do `log2(10)` ops for both query and update, so about 7-8 total\n* and another one to pop\n* and the query and update ops are more complicated than their brute force counterparts\n\nSo overall this solution does *more* work per character than the brute force solution.\n\nI expect this would change if the alphabet for the strings were all 62 alphanumeric characters, then `O(62/2) = O(31)` on average would be probably be more expensve than `O(log(62)*2) ~ O(10)` operations.\n\nFor bigger problems like all ASCII or unicode characters or tokenized inputs, the savings could be dramatic.\n\n# Code\n```\nclass Solution:\n    def isTransformable(self, s: str, t: str) -> bool:\n        # op: sort i..j\n        # we don\'t care about the count of operations, so we just care if it\'s possible\n        #    min op is swapping adjacent\n\n        # so can we get t from s with some bubble sort operations?\n\n        # for each char in t:\n        #    need to move a copy of c in s to the front\n        #    so there can be no copies of lower chars in the way\n        #    "in the way" means in positions that *don\'t* match t (yet)\n\n\n        # e.g. at some intermeidate state\n        #    s = .........abc\n        #    t = .........cba\n        #        ---------\n        #          /\n        #  these are set,\n        #  don\'t count these\n\n        # brute force: for t[i]: look through s[i:] for a copy of t[i]\n        #    if there\'s a lower char in the way, return False\n        #    skip over chars already moved\n        #    then find the character and move it\n        # that\'s O(N) per operation\n\n        # to be faster: if we find t[i] at s[j], then chars below j in s have index += 1, later chars have no index change\n        #   so we can track the updated indices via cumulative offsets\n\n        # then when we need to match t[i], look at the current index of the next copy of t[i] in s (deque, log(n) offset query)\n        # and check if there are any extant copies of lower chars in the way\n        \n        # since the rel orders of unplaced chars don\'t change, we actually don\'t need to check the offsets! We just\n        # need to know if the next copy of t[i] in s, call it index k, is higher than the min *unplaced/unmatched* index\n        # of any lower character "in the way", i.e. lower\n        #   So in log or constant time we want  min_{d\' < d} (next unplaced index of d)\n        # this is a "range query", which means Fenwick or segment tree\n        # the min unplaced for each char rises over time, so changes have to progagate up the tree\n        # but depend on all children. If it depends on all, we should use a segment tree b/c each node has just 2 children\n\n        N = len(s)\n\n        # get indices for all characters; could be lazy for best-case improvement from O(N) to O(1) space\n        idxs = [deque() for _ in range(10)] \n        for i, c in enumerate(s): idxs[int(c)].append(i)\n\n        # segment tree to quickly get earliest index of chars in some range\n        # use next position == N to signal "there\'s no such min"\n        A = 10 # alphabet size\n        st = [0]*(2*A) # leaves at o+A, root at 1\n        for d in range(10):\n            st[d+A] = idxs[d][0] if idxs[d] else N\n        for n in range(A-1, 0, -1): st[n] = min(st[2*n], st[2*n+1])\n\n        def getMin(lo: int, hi: int) -> int:\n            lo += A\n            hi += A + 1\n            ans = st[lo]\n            while lo < hi:\n                # only include lo,hi node if [lo..hi) does not include the parent\n                if lo & 1:\n                    ans = min(ans, st[lo])\n                    lo += 1\n\n                if hi & 1:\n                    ans = min(ans, st[hi-1])\n\n                lo >>= 1\n                hi >>= 1\n\n            return ans\n\n        def setVal(d: int, v: int) -> None:\n            n = d+A\n            st[n] = v\n            n >>= 1\n            while n:\n                old = st[n]\n                st[n] = min(st[2*n], st[2*n+1])\n                if st[n] == old: break # stop propagating upward if min didn\'t change\n                n >>= 1\n\n        for c in t:\n            d = int(c)\n            if not idxs[d]: return False # there\'s no such copy of c (so s is not an anagram of t)\n            k = idxs[d].popleft()\n            if getMin(0, d-1) < k: return False # min pos of char below d is less than k: it\'s in the way, can\'t swap past it\n            setVal(d, idxs[d][0] if idxs[d] else N)\n\n        return True\n\n        # TC: O(N) setup. Then for each char, we\n        #     convert to int and check deque in O(1)\n        #     getMin in log(d) time == log(A) time for alphabet size A\n        #     setVal in log(A) time\n        #   so it\'s O(N*log(A)) for A == 10 (or maybe 9 if there are no zeros)\n\n\n```
['Python3']