643. Where the Dominoes Come to Rest
A row of dominoes is described by a string: L for one pushed left, R for one pushed right,
and . for one still standing.
Each second, every standing domino that is being pushed from exactly ONE side falls that way. A domino falls left when the domino immediately to its RIGHT is falling left, and falls right when the domino immediately to its LEFT is falling right. Note which side each rule reads: a domino falling left topples the one behind it, not the one it is falling towards. A domino pushed from both sides in the same second stays standing, because the forces balance.
Print the row once nothing more changes.
RR.L -> RR.L the middle is pushed from both sides
.L.R...LR..L.. -> LL.RR.LLRRLL..
.R...L. -> .RR.LL.
## Do not simulate second by second
Simulating each second is correct and costs O(n) per second with up to O(n) seconds, so
O(n^2). Every standing run settles according to the two pushed dominoes that BRACKET it, and
that can be read off directly.
## Look at consecutive pushed dominoes
Pad the row with an imaginary L before the start and an R after the end. Those are the
boundaries: nothing pushes inwards from outside the row, and these padding characters have
exactly that effect.
Now walk two pointers over consecutive non-standing positions, i then j, with only dots
between them. Four cases cover everything:
L ... L -> all fall left the left pushes nothing, the right pulls all
R ... R -> all fall right
L ... R -> nothing moves they push outwards, away from the gap
R ... L -> meet in the middle half right, half left, and if the gap is
odd the exact centre stays standing
## Why the padding is the right boundary
L at the far left means "the outside is falling away from the row", so a leading gap followed
by an L is the L ... L case and falls left, which is correct: the real L drags it.
Symmetrically the trailing R. Handling the ends with padding rather than special cases
removes two branches and the off-by-one errors that come with them.
## The odd gap
In the R ... L case with a gap of g, the answer is g/2 copies of R, then g % 2 dots,
then g/2 copies of L. The middle domino of an odd gap is reached by both sides on the same
second and therefore stays up.
That is the case worth tracing: R.....L becomes RRR.LLL, not RRRLLLL.
## Cost
Time O(n). Space O(n) for the output.
Constraints - `1 ≤ length ≤ 200000` - the row contains only `L`, `R` and `.`
Input
One line containing the row, made only of the characters L, R and ..
Output
Print the final row on one line.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.