Falling Domino Row

Medium

A row of dominoes is standing upright. At the start, some of them are pushed at the same moment, as described by the string row: - 'L': the tile was pushed to the left; - 'R': it was pushed to the right; - '.': the tile was left alone. Every second, a tile falling left knocks its left neighbour over to the left, and a tile falling right knocks its right neighbour over to the right. If a standing tile is hit from both sides in the same second, the forces cancel and it stays upright. Pushes have no effect on tiles that are already falling or have fallen. Return a string in the same format describing the final state of the row.

Example 1

row="R...L" → 'RR.LL'

The two end tiles fall towards each other. One second later their neighbours fall, and the middle tile is hit from both sides at once, so it stays upright.

Example 2

row=".L..R." → 'LL..RR'

The L knocks over only tile 0 to its left, the R only the last tile. Nothing pushes the tiles in between.

Example 3

row="RL.R" → 'RL.R'

Constraints

1 ≤ len(row) ≤ 10⁵
Each character of row is 'L', 'R' or '.'

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Two Pointers String Dynamic Programming

Similar problems

Longest Mirror Fragment Medium Counting Palindromic Pieces of a String Medium Word Growth Chain Medium Nearly Matching Picks Medium Erasable Marked Letters Medium

Input

row="R...L"

Expected

'RR.LL'

Run checks the first 3 tests in your browser. Submit checks all 165 tests on the server, hidden ones included.