C++ - O(N) - Explained for beginners with examples
Logic\n- The best way to solve this is to swap two numbers, which will help us to maintain the order.\n- A number can be moved to its left till it finds a small
**Logic**\n- The best way to solve this is to swap two numbers, which will help us to maintain the order.\n- A number can be moved to its left till it finds a smaller number, example, for case of 12543, 3 can only come till index 2 \n- If we will go greedily and check if ith index of t is possible or not, then if we will reach the end, then we will return true.\n\n**Methodology**\nMaintain 10 queues q[0], q[1],...q[9], the queues will store the indices where ith digit is found in s.\nFor each t[i], we check q[numbers less than t[i]], if any of them have a smaller index than q[t[i]], then return false, else pop from q[t[i]]\n\n**Code**\n```\nclass Solution {\npublic:\n    bool isTransformable(string s, string t) {\n        vector<queue<int>> vNumIndicies(10);\n        for(int i = 0; i < s.size(); i++)\n            vNumIndicies[s[i] - \'0\'].push(i);\n        for(int i = 0; i < t.size(); i++){\n            if(vNumIndicies[t[i] - \'0\'].empty())\n                return false;\n            for(int j = 0; j < t[i] - \'0\'; j++){\n                if(!vNumIndicies[j].empty() && vNumIndicies[j].front() < vNumIndicies[t[i] - \'0\'].front())\n                    return false;\n            }\n            vNumIndicies[t[i] - \'0\'].pop();\n        }\n        return true;\n    }\n};\n```\n\n**Example 1**\nInput: s = "84532", t = "34852"\nusing s, we can create our queues as:\nq[2] = 4\nq[3] = 3\nq[4] = 1\nq[5] = 2\nq[8] = 0\n\nNow, \nfor i = 0, t[i ] = 3, q[t[i]] = 3, and q[j], where j < t[i], possible queues are q[2], which is 4, which is greater than q[t[i]]. Hence, continue, pop from q[3].\n\nfor i = 1, t[i ] = 4, q[t[i]] = 1, and q[j], where j < t[i], possible queues are q[2], which is 4, and q[3], which is empty now, hence, none of them is smaller than q[t[i]]. Hence, continue, pop from q[4].\n\nfor i = 2, t[i ] = 8, q[t[i]] = 0, its already zero, none can be greater than this, pop from q[8].\n\nfor i = 3, t[i ] = 5, q[t[i]] = 2, and q[j], where j < t[i], possible queues are q[2], which is 4, and q[3] and q[4], which is empty now, hence, none of them is smaller than q[t[i]]. Hence, continue, pop from q[5].\n\nfor i = 4, t[i] = 2, q[t[i]] = 4, and q[j], where j < t[i], no queues possible, hence, pop from q[2].\n\nAs we have reached the end, hence return true.\n\n**Example 2**\nInput: s = "12345", t = "12435"\nusing s, we can create our queues as:\nq[1] = 0\nq[2] = 1\nq[3] = 2\nq[4] = 3\nq[5] = 4\n\nNow,\nfor i = 0, t[i] = 1, q[t[i]] = 0, and q[j], where j < t[i], no queues possible, hence, pop from q[1].\n\nfor i = 1, t[i] = 2, q[t[i]] = 1, and q[j], where j < t[i], possible queue is q[1], which is empty, hence, pop from q[2].\n\nfor i = 2, t[i] = 4, q[t[i]] = 3, and q[j], where j < t[i], possible queues are, q[1] (empty), q[2] (empty), q[3] = 2, which is less than q[t[i]], hence, return false.
['Queue', 'C']