[Java] O(m) Solution, Intuition and detailed explanation
\n/**\n    1. intuition\n        if we do one time iteration, and reach index i in string s, \n        how can we know start from which index j in s, \n        
```\n/**\n    1. intuition\n        if we do one time iteration, and reach index i in string s, \n        how can we know start from which index j in s, \n        and start from (x0, y0) to execute instructions [s[j], s[i]], to make make (x0+dx, y0+dy) out of range,\n        dx and dy are acuumulated difference in x, y direction\n        if that is the case, we can execute [s[j], s[i-1]] so we can execute at most i-j instructions, ans[j] = i-j\n    \n    2. how to improve\n        brute force is to simulate the process, that requires us compute dx and dy for each i (as start index) in s\n        what if we can reuse dx, dy? how can we reuse dx, dy?\n    \n    3. backward thinking\n        to reuse dx, dy, we need change the \'start position\'\n        start from (x0, y0) and execute s[i] is equivalent to \n        start from (x0-dx, y0-dy) and execute all instrcutions from s[0] to s[i]\n    \n    3. convert \'execeed range\' condition\n        forward thought:\n            from some point, x == -1 or x == n or y == -1 or y == n, it means they are outside\n        backward thought:\n            accumulated difference is dx and dy, if at some point the starting point is \n                n-dx:     execute s[0] to s[i], will make x == n\n                -dx-1:    execute s[0] to s[i], will make x == -1\n                n-dy:     execute s[0] to s[i], will make y == n\n                -dy-1:    execute s[0] to s[i], will make y == -1\n  \n    4. time:   O(m)  \n       space:  O(m)\n*/\nclass Solution {\n    public int[] executeInstructions(int n, int[] startPos, String s) {\n        int m = s.length();\n        \n        int x0 = startPos[0], y0 = startPos[1];\n        int dx = 0, dy = 0;\n        Map<Integer, Set<Integer>> xMap = new HashMap<>();\n        Map<Integer, Set<Integer>> yMap = new HashMap<>();\n        \n        // init ans\n        // eg. from 0 we can execute at most m instructions, from 1 at most m-1 instructions...\n        int[] ans = new int[m];\n        for (int i = 0; i < m; i++) {\n            ans[i] = m - i;\n        }\n        \n        xMap.putIfAbsent(x0, new HashSet<>());\n        yMap.putIfAbsent(y0, new HashSet<>());\n        xMap.get(x0).add(0);\n        yMap.get(y0).add(0);\n        \n        for (int i = 0; i < s.length(); i++) {\n            if (s.charAt(i) == \'L\') dy -= 1;\n            if (s.charAt(i) == \'R\') dy += 1;\n            if (s.charAt(i) == \'U\') dx -= 1;\n            if (s.charAt(i) == \'D\') dx += 1;\n            \n            xMap.putIfAbsent(x0-dx, new HashSet<>());\n            yMap.putIfAbsent(y0-dy, new HashSet<>());  \n            xMap.get(x0-dx).add(i+1);\n            yMap.get(y0-dy).add(i+1);\n            \n            // starting from some index j, may exceed range, find thouse index j and update ans[j]\n            processOutbound(ans, xMap, n-dx, i);\n            processOutbound(ans, yMap, n-dy, i);\n            processOutbound(ans, xMap, -dx-1, i);\n            processOutbound(ans, yMap, -dy-1, i);\n        }\n        \n        return ans;\n    }\n   \n    private void processOutbound(int[] ans, Map<Integer, Set<Integer>> map, int pos, int i) {\n        if (!map.containsKey(pos)) return;\n        for (int j : map.get(pos)) {\n            ans[j] = Math.min(ans[j], i - j);\n        }   \n        map.put(pos, new HashSet<>());\n    }\n}\n```
[]