[Python] Back tracking, O(m) Solution
\n# Solution 1: Brute force\nHelper fucntion test(i) to check the the number of instructions the robot can execute,\nif the robot begins executing from the ith 
\n# **Solution 1: Brute force**\nHelper fucntion `test(i)` to check the the number of instructions the robot can execute,\nif the robot begins executing from the `i`th instruction in s.\n\nTime `O(m^2)`\nSpace `O(1)`\n\n**Python**\n```py\n    def executeInstructions(self, n, start, s):\n        na = len(s)\n        def test(i):\n            res = 0\n            x,y = start\n            for j in xrange(i, na):\n                o = s[j]\n                if o == \'L\': y -= 1\n                if o == \'R\': y += 1\n                if o == \'U\': x -= 1\n                if o == \'D\': x += 1\n                if not (0 <= x < n and 0 <= y < n):\n                    return j - i\n            return na - i\n        return map(test, range(na))\n```\n<br>\n\n# **Solution 2: Multiplication**\nShared by @OOTTF:\nFor every start point `i`,\nrecord the position after 2^k steps,\nand extrene position in the 4 directions.\n\nTime `O(mlogm)`\nSpace `O(mlogm)`\n<br>\n\n# **Solution 3: O(m) solution**\nStarting from the first order,\nfind the difference on x-axis and y-axis\n\n`count` reocrd the postion with start index.\nFor example,\n`count[x0, None].add(0)`, means that at index `0`, we are at x-axis `x0`.\n`count[None, y0].add(0)`, means that at index `0`, we are at x-axis `y0`.\n\nThe tricky and the difficult point for this solution is that,\nstarting at `(x0,y0)` and excute from `s[i]`,\nis same as\nstarting at `(x0 - x, y0 - y)` and excute from `s[0]`.\nThis process has a sense of backtracking.\n\nNow at step `s[i]` we have delta `(x, y)`,\nif `x > 0`, we have moved down, and making points starting as x-axis `n-x` off the grid.\nif `y > 0`, we have moved down, and making points starting as x-axis `n-y` off the grid.\nif `x < 0`, we have moved down, and making points starting as x-axis `-x-1` off the grid.\nif `y < 0`, we have moved down, and making points starting as x-axis `-y-1` off the grid.\n\nAt the end of each step, we clean all starting point already off the grid.\nThe ensures the whole solution is `O(m)`, where we add only once and clean only once.\n\nTime `O(m)`\nSpace `O(m)`\n<br>\n\n\n**Python**\n```py\n    def executeInstructions(self, n, start, s):\n        ns = len(s)\n        (x0, y0), (x, y) = start, (0, 0)\n        res = range(ns, 0, -1)\n        count = collections.defaultdict(set)\n        count[x0, None].add(0)\n        count[None, y0].add(0)\n        for i in xrange(ns):\n            if s[i] == \'L\': y -= 1\n            if s[i] == \'R\': y += 1\n            if s[i] == \'U\': x -= 1\n            if s[i] == \'D\': x += 1\n            count[x0 - x, None].add(i + 1)\n            count[None, y0 - y].add(i + 1)\n            for key in [(n-x, None), (None, n-y), (-x-1, None), (None, -y-1)]:\n                for j in count[key]:\n                    if res[j] > i - j:\n                        res[j] = i - j\n                count[key] = set()\n        return res\n```\n
['Python']