C# - 89ms - O(n) - Solution
Intuition\n Describe your first thoughts on how to solve this problem. \nSince the goal is to determine whether it\'s possible to transform the string by rearra
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nSince the goal is to determine whether it\'s possible to transform the string by rearranging substrings, it\'s not required to actually perform the sorting. Instead, the focus should be on identifying the rules that allow for sorting a string in such a way that, if any of these rules are broken, the string cannot be transformed.\n\nIt made sense to traverse the string in reverse order because the possibilities for rearrangement are determined at the end of the string. Additionally, if a number is already in its correct position, there will be no need for further sorting.\n\nTo determine whether the string can be transformed, one way to understand the problem is to consider the simplest method, where moving a value always involves using a pair. The pairs would be swapped until the value reaches its correct position in the string.\n\nThus, to perform a new pairwise swap, the value on the left must always be biggest than the value on the right $$s[i] > s[i + 1]$$, so $$[2,1] => [1,2]$$. If the value on the right is greater than the one on the left, then the pair cannot be transformed. If you choose this pair $$[1,2]$$, it always gonna be $$[1,2]$$.\n\nFurthermore, if we want to move a certain value, it must adhere to two rules.\n\nTo do this, consider that if the last values of string $$s$$ match the values of string $$t$$, then they do not need to be considered, e.g. $$s = [1234]$$ and $$t = [1324]$$, i just consider: $$s = [123]$$ and $$t = [132]$$. Also, if a change positions a value correctly at the end of string $t$, it can be disregarded as well, like $$s = [384759], t = [438579]$$, if change $$[75] => [57]$$ we got $$s = [384579], t = [438579]$$, so we consider $$s = [348], t = [438]$$ . Therefore, in the following rules, whenever the end of string $$s$$ or $$t$$ is mentioned, understand it as referring to the portion that still needs modification, ignoring the values that are already correct.\n\nIn summary, the rules are as follows:\nGiven an index $$a$$, if $$s[a]$$ is greater than all the values to the right of $$t$$, then no value $$s[x]$$ with $$x < a$$ can pass $$s[a]$$. $ return \\space false$.\nAnother case is if $$s[a] = t[x]$$ with $$x > a$$ \u2014 in other words, $$s[a]$$ is to the right of $$t$$ \u2014 and if $$s[a]$$ is smaller than all the values $$s[y]$$ with $$y > a$$, then $$s[a]$$ will never reach index $$x$$. $ return \\space false$.\n\nNow with a bit more detail:\n\n1. [RULE 1] Consider an index $a$ of $$s$$. This value $$(s[a])$$ must be less than or equal to the maximum value of the elements to the end of the string $$t$$, $$s[a] <= Max(t[a + 1], ..., t[a + n])$$ where $$n$$ is the length till the end of string $$t$$. This is because if the opposite happens \u2014 i.e., the value is greater than the maximum of the values to the end of the string $$t$$ \u2014 then the value from $$s$$ will occupy at least one of those positions, causing at least one required value in $$t$$ to be excluded.\n    Example: \n    $$s = [24851], t = [85412]$$, consider $$index = 3$$\n    $$s[2] = 8 > Max(1, 2)$$\n    It\u2019s not possible to move the number $$2$$ past the number $$8$$. In other words, it would only be possible to organize $$s$$ if the 2 were already to the right of the number $$8$$.\n\n2. [RULE 2] The second rule is that given a value in $$s$$ $$(s[a])$$, as long as it is within string $$t$$, from its index to the end of the string, $$s[a] \\in \\{x : x = t[y], y >= a\\}$$, the value in $$s$$ must be greater than or equal to the minimum of the values in $$s$$ to the end of string $$s[a] >= Min(s[a + 1], ..., s[a + n])$$ where $$n$$ is the length till the end of string $$s$$.\nIn other words, if it is smaller than the minimum of the values in $$s$$ above index $a$ to the end, it means it cannot be moved to the right, since all the values to the right are greater than it. Therefore, it cannot be sorted to the right, and any further reordering will only allow it to move to the left, making the transformation impossible.\n    Example:\n    $$s = [24185], t = [85412]$$, consider $$index = 2$$\n    $$s[2] = 1$$ its equal $t[3] = 1$, with index $ 3 > 2$\n    $$s[2] = 1 < Max(8, 5)$$\n    It\u2019s not possible to move the number $$1$$ past the number $$8, 5$$. In other words, it would only be possible to organize $$s$$ if the $$1, 2$$ were already to the right of the number $$8$$.\n\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\nFor the implementation of the algorithm, I chose to create two arrays: \n- one for the available values in $$s - available$$.\n-  another for the required values in $$t - required$$. \n\nI also created two variables to hold the minimum of the available values $$(minAvailable)$$ and the maximum of the required values $$(maxRequired)$$.\n\nWith these variables, the process works as follows:\n\n1. Traverse all elements of the strings in reverse order.\n2. For each index, retrieve the respective values in $$s$$ and $$t$$.\n3. Update the maximum required value and the minimum available value.\n4. Check [RULE 1]: if the value in $$s$$ is greater than the maximum required value, then the string cannot be transformed, so $$return \\space false$$.\n5. Add the values of $s$ and $t$ to the $available$ and $required$ arrays, respectively, to proceed with the possibility of shifting. At this index, for each value, increment by 1, so that if there are repetitions, the value of $available/required$ at that index will reflect the number of values that have not yet been evaluated.\n6. If the value in $s$ is identified as a required value that has not yet been replaced, then check [RULE 2]:\n    *  If the value in $s$ is less than the minimum value in the available array, then the string cannot be transformed.\n    *  After evaluating [RULE 2], decrement the value of $s$ in $t$, ensuring that this value can be moved without breaking any rules.\n7. If the value of $t$ is in the available array, also decrement the values in the $available$ and $required$ arrays, as they can now be moved without breaking any rules.\n8. After traversing the string $t$, to ensure the string is transformable, check if the sum of the $required$ array equals zero. If true, it confirms that all values can be adjusted, and the string is transformable.\n9. If the sum of the required array is different from zero, then the string cannot be transformed, as some value in the required array has not been fulfilled.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nI think it\'s $$O(n)$$\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nI think it\'s $$O(n)$$\n\n# Code\n```\npublic class Solution {\n    public bool IsTransformable(string s, string t) {\n        var required = new int[10];\n        var available = new int[10];\n        int minAvailable = 10;\n        int maxRequired = 0;\n\n        for(var index = s.Length - 1; index >= 0; index --)\n        {\n            var (sValue, tValue) = SetValues(index);\n            minAvailable = GetMinAvailable();\n            maxRequired = GetMaxNecessary(sValue); \n            if(sValue > maxRequired) return false;\n            Increase(sValue, tValue);\n            if(HasNecessary(sValue))\n            {\n                if(sValue < minAvailable) return false;\n                Decrease(sValue);\n            }\n            if(HasAvailable(tValue)) Decrease(tValue);\n        }\n\n        if(required.Sum() == 0) return true;\n\n        return false;\n\n        bool HasNecessary(int sValue)\n        {\n            return required[sValue] > 0;\n        }\n\n        bool HasAvailable(int tValue)\n        {\n            return available[tValue] > 0;\n        }\n\n        void Increase(int sValue, int tValue){\n            available[sValue] ++;\n            required[tValue] ++;\n        }\n\n        void Decrease(int value){\n            required[value] --;\n            available[value] --;\n        }\n\n        int GetMinAvailable()\n        {\n            var value = Array.FindIndex(available, 0, x => x > 0);\n            if(value == -1) value = 0;\n            return value;\n        }\n\n        int GetMaxNecessary(int sValue)\n        {\n            var value = Array.FindLastIndex(required,sValue, x => x > 0);\n            if(value == -1) value = 9;\n            return value;\n        }\n\n        (int, int) SetValues(int index)\n        {\n            return (s[index] - \'0\', t[index] - \'0\');\n        }\n    }\n}\n```
['C#']