2153. The Run Your Own Piece Closes

A row of n cells holds . for empty, A for one player's piece and B for the other's. k placements are made, in the order given. Each names a player and a cell index counting from 0.

A placement is carried out like this:

1. if the cell is not empty, the placement is ILLEGAL: nothing changes at all 2. otherwise the player's piece is written into that cell 3. then, looking LEFT from it and looking RIGHT from it, independently: read outward while the cells hold the OPPONENT's piece if that run is non-empty AND the cell immediately beyond it holds the player's OWN piece, every piece in the run changes to the player's if the run is empty, or it runs off the end of the row, or the cell beyond it is empty, nothing changes in that direction

Both directions are decided from the row as it stands immediately after step 2 and BEFORE either flip is applied, so a capture on one side can never create or destroy a capture on the other.

Print the row after all k placements.

``` A.BBA place A at 1 -> AAAAA

looking left from cell 1: cell 0 holds A, which is the player's own piece, so the run of opponent pieces is empty and nothing is captured looking right: cells 2 and 3 hold B, cell 4 holds A, so both flip

..BB. place A at 1 -> .ABB.

looking right: cells 2 and 3 hold B and then the row ends with an empty cell, so the run is not closed and nothing flips ```

## What most people try first

Flipping as the scan walks, rather than collecting the run and flipping once the closing piece has been confirmed. On ..BB. that converts cells 2 and 3 to A and only then discovers there is no closing A, leaving the row wrong and with no easy way back.

The second common slip is deciding the second direction from the already flipped row. Consider placing A at index 2 of AB.BA: left sees B at 1 closed by A at 0, right sees B at 3 closed by A at 4. Both flip, and the answer is AAAAA. If the left flip is applied first and the right scan then reads the new row, the answer happens to be the same here, but the rule has become order dependent, and on other inputs it is not the same. Pinning both directions to the pre-flip row removes the question.

## The method

if row[at] is not '.': skip this placement row[at] = me before = a copy of row flips = empty list for step in (-1, +1): j = at + step run = empty list while j is inside the row and before[j] == opponent: add j to run j = j + step if run is non-empty and j is inside the row and before[j] == me: add run to flips for j in flips: row[j] = me

## Why it is correct

The rule as written is a function of the row immediately after the placement, so the only thing to establish is that the code evaluates it on exactly that row and writes nothing until both directions have been decided.

Taking the copy before after step 2 gives precisely the row the rule names. Both scans read only before, so neither can see the other's result, and the collected flips therefore describes the same set of cells whichever order the two directions are examined in. The writes happen after both scans, so they cannot affect either. That is what makes the answer independent of the direction order, which is the property the statement promises.

The closure test is also exactly the rule: the loop stops at the first cell that is not the opponent's, so j is either off the end of the row or holds . or holds the player's own piece. Only the last of those three closes the run, and only a non-empty run is a capture, so both conditions are needed and neither is redundant.

## The boundary that breaks a careless implementation

A run that reaches the end of the row is not closed. A run closed by an empty cell is not closed either. And a placement next to its own piece captures nothing in that direction, because the run of opponent pieces is empty: AA is not a capture of zero pieces that still counts.

An illegal placement is skipped entirely, including its captures. It does not flip anything and it does not consume anything.

## Cost

Each placement scans outward at most the width of the row, so O(n) per placement and O(n k) overall, with O(n) memory.

Constraints - `1 ≤ n ≤ 2000` - `1 ≤ k ≤ 2000` - every character of the starting row is `.`, `A` or `B` - the player on each placement is `A` or `B` - `0 ≤ the cell index < n` - a placement onto a cell that is not empty changes nothing at all - both directions are decided from the row immediately after the piece is placed and before any flip