<p>There is an <code>n x n</code> grid, with the top-left cell at <code>(0, 0)</code> and the bottom-right cell at <code>(n - 1, n - 1)</code>. You are given the integer <code>n</code> and an integer array <code>startPos</code> where <code>startPos = [start<sub>row</sub>, start<sub>col</sub>]</code> indicates that a robot is initially at cell <code>(start<sub>row</sub>, start<sub>col</sub>)</code>.</p>

<p>You are also given a <strong>0-indexed</strong> string <code>s</code> of length <code>m</code> where <code>s[i]</code> is the <code>i<sup>th</sup></code> instruction for the robot: <code>&#39;L&#39;</code> (move left), <code>&#39;R&#39;</code> (move right), <code>&#39;U&#39;</code> (move up), and <code>&#39;D&#39;</code> (move down).</p>

<p>The robot can begin executing from any <code>i<sup>th</sup></code> instruction in <code>s</code>. It executes the instructions one by one towards the end of <code>s</code> but it stops if either of these conditions is met:</p>

<ul>
	<li>The next instruction will move the robot off the grid.</li>
	<li>There are no more instructions left to execute.</li>
</ul>

<p>Return <em>an array</em> <code>answer</code> <em>of length</em> <code>m</code> <em>where</em> <code>answer[i]</code> <em>is <strong>the number of instructions</strong> the robot can execute if the robot <strong>begins executing from</strong> the</em> <code>i<sup>th</sup></code> <em>instruction in</em> <code>s</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/12/09/1.png" style="width: 145px; height: 142px;" />
<pre>
<strong>Input:</strong> n = 3, startPos = [0,1], s = &quot;RRDDLU&quot;
<strong>Output:</strong> [1,5,4,3,1,0]
<strong>Explanation:</strong> Starting from startPos and beginning execution from the i<sup>th</sup> instruction:
- 0<sup>th</sup>: &quot;<u><strong>R</strong></u>RDDLU&quot;. Only one instruction &quot;R&quot; can be executed before it moves off the grid.
- 1<sup>st</sup>:  &quot;<u><strong>RDDLU</strong></u>&quot;. All five instructions can be executed while it stays in the grid and ends at (1, 1).
- 2<sup>nd</sup>:   &quot;<u><strong>DDLU</strong></u>&quot;. All four instructions can be executed while it stays in the grid and ends at (1, 0).
- 3<sup>rd</sup>:    &quot;<u><strong>DLU</strong></u>&quot;. All three instructions can be executed while it stays in the grid and ends at (0, 0).
- 4<sup>th</sup>:     &quot;<u><strong>L</strong></u>U&quot;. Only one instruction &quot;L&quot; can be executed before it moves off the grid.
- 5<sup>th</sup>:      &quot;U&quot;. If moving up, it would move off the grid.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/12/09/2.png" style="width: 106px; height: 103px;" />
<pre>
<strong>Input:</strong> n = 2, startPos = [1,1], s = &quot;LURD&quot;
<strong>Output:</strong> [4,1,0,0]
<strong>Explanation:</strong>
- 0<sup>th</sup>: &quot;<u><strong>LURD</strong></u>&quot;.
- 1<sup>st</sup>:  &quot;<u><strong>U</strong></u>RD&quot;.
- 2<sup>nd</sup>:   &quot;RD&quot;.
- 3<sup>rd</sup>:    &quot;D&quot;.
</pre>

<p><strong class="example">Example 3:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/12/09/3.png" style="width: 67px; height: 64px;" />
<pre>
<strong>Input:</strong> n = 1, startPos = [0,0], s = &quot;LRUD&quot;
<strong>Output:</strong> [0,0,0,0]
<strong>Explanation:</strong> No matter which instruction the robot begins execution from, it would move off the grid.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>m == s.length</code></li>
	<li><code>1 &lt;= n, m &lt;= 500</code></li>
	<li><code>startPos.length == 2</code></li>
	<li><code>0 &lt;= start<sub>row</sub>, start<sub>col</sub> &lt; n</code></li>
	<li><code>s</code> consists of <code>&#39;L&#39;</code>, <code>&#39;R&#39;</code>, <code>&#39;U&#39;</code>, and <code>&#39;D&#39;</code>.</li>
</ul>

class Solution:
    def executeInstructions(self, n: int, startPos: List[int], s: str) -> List[int]:
        # sr, sc = startPos

        # # brute force: simulate from all starting locs i

        # # smarter: for range i..j we'll have some max excursion in all four directions
        # #    if the max excursion exceeds the bounds then we need to shrink the bounds

        # # we might be able to efficiently query this by looking at net LRUD moves in a range of of moves
        # # except we have to be careful about NEVER exceeding the bounds. ouch.

        # m = len(s)
        # out = [0]*m
        # for i in range(m):
        #     r, c = sr, sc
        #     for j in range(i, m):
        #         if s[j] == 'U':
        #             if r: r -= 1
        #             else: break
        #         elif s[j] == 'D':
        #             if r < n-1: r += 1
        #             else: break
        #         elif s[j] == 'L':
        #             if c: c -= 1
        #             else: break
        #         else:
        #             if c < n-1: c += 1
        #             else: break
        #     else:
        #         # didn't break: all m-i moves starting at i worked
        #         out[i] = m-i
        #         continue

        #     # broke at j: i..j-1 worked
        #     out[i] = j-i

        # return out

        #### super clever version, horribly explained though, virtual positions and whatnot... WTF??

        # for not going off the left: we can't have a cumulative left - right count that exceeds col

        # so suppose we have .......LLLLRLLLRRRLLLRLRLLLLLRRLLLLLLLRRLLRL
        #                           123434565434565656789A989ABCDEFEDEFEF  <- cumulative left count
        #
        # if current col is 5 then we blow up where the cumulative left count FIRST hits 6
        # how do we get cumulative left? Suffix sums!
        #      if we know the current cumulative left count all the way to the right is L
        #      then we will blow up where the cumulative left count was most recently L+6 (at j)
        #
        #   suppose we're at some net position relative to the end of the string in l and r
        #   and suppose we can make 0 moves left
        #   then the next time we are at 1 fewer left (c-1) is when we'll blow up

        dirs = {'U': (-1, 0), 'D': (1, 0), 'L': (0, -1), 'R': (0, 1)}
        m = len(s)

        netR = {0: m}
        netD = {0: m}
        
        sr, sc = startPos
        maxUp, maxLeft = sr, sc
        maxDn, maxRight = n-1-sr, n-1-sc

        #       L  L  L  R  R  L  R  L  L
        #       0  1  2  3  4  5  6  7  8  9
        #                0 -1 -2 -1 -2 -1
        #
        # if we can't move right: find first subarray where we moved net one right
        # which means the first index where the suffix sum has one FEWER right move
        # we aren't taking move j, and we aren't taking the move that got us to j
        # hence j-i+1-2 moves
        r = 0 # net right and down moves to end
        d = 0
        out = [0]*m
        for i in range(m-1, -1, -1):
            d += dirs[s[i]][0]
            r += dirs[s[i]][1]

            # moves i: moves us d down and r right; we're at d,r
            #      e.g.     545432345678987654321
            #               i        j
            #                       * <- last valid move
            #                     number of moves is j-i-1 because 5 is net of/after move i
            
            maxMoves = m-i
            if d-maxDn-1 in netD: maxMoves = min(maxMoves, netD[d-maxDn-1]-i-1)
            if d+maxUp+1 in netD: maxMoves = min(maxMoves, netD[d+maxUp+1]-i-1)
            if r-maxRight-1 in netR: maxMoves = min(maxMoves, netR[r-maxRight-1]-i-1)
            if r+maxLeft+1 in netR: maxMoves = min(maxMoves, netR[r+maxLeft+1]-i-1)

            netR[r] = i
            netD[d] = i

            out[i] = maxMoves

        return out
60