[Java] Short, Clean O(nlogn) Solution using Bubbling + Fenwick Tree, Detailed Explanation
The main observation here is that we can always bubble a larger digit back as long as it is bubbling over smaller digits (and that if a transformation is possib
The main observation here is that we can always bubble a larger digit back as long as it is bubbling over smaller digits (and that if a transformation is possible, it can always be performed via such bubbling). The pain point is implementing an algorithm that does better than quadratic time. \n\nHere we take advantage of there only being 10 possible digits in the strings, and each time we bubble a larger digit back, we increment the position of each digit originally behind the bubbled digit. We perform this incrementing indirectly through a Fenwick Tree, which allows us to calculate the total number of digits ahead of any digit that have been bubbled back, which is equivalent to the offset we should add to the digit\'s original index in the string s.\n\n```\nclass Solution {\n    class FenwickTree {\n        int[] arr;\n        \n        public FenwickTree(int n) {\n            arr = new int[n+1];\n        }\n        \n        public void add(int i) {\n            i++;\n            while (i < arr.length) {\n                arr[i]++;\n                i += i & -i;\n            }\n        }\n        \n        public int sumUntil(int i) {\n            i++;\n            int ret = 0;\n            while (i > 0) {\n                ret += arr[i];\n                i -= i & -i;\n            }\n            return ret;\n        }\n    }\n    \n    public boolean isTransformable(String s, String t) {\n        int n = s.length();\n        FenwickTree FT = new FenwickTree(n);\n        List<Deque<Integer>> L = new ArrayList();\n        for (int i = 0; i < 10; i++) L.add(new ArrayDeque());\n        for (int i = 0; i < s.length(); i++) {\n            int cur = s.charAt(i) - \'0\';\n            L.get(cur).add(i);\n        }\n        for (int i = 0; i < t.length(); i++) {\n            int cur = t.charAt(i) - \'0\';\n            Deque<Integer> D = L.get(cur);\n            if (D.isEmpty()) return false;\n            int idx = D.peekFirst(), idxEff = FT.sumUntil(n-1) - FT.sumUntil(idx) + idx; \n            for (int j = cur-1; j >= 0; j--) {\n                Deque<Integer> D2 = L.get(j);\n                if (!D2.isEmpty() && FT.sumUntil(n-1) - FT.sumUntil(D2.peekFirst()) + D2.peekFirst() < idxEff) return false;\n            }\n            FT.add(idx);\n            D.removeFirst();\n        }\n        return true;\n    }\n}\n```
[]