Show problems as
Classic problem #838MediumTwo PointersStringDynamic Programming

Push Dominoes

Real-world version: Where the Pushed Tiles Settle
Tracked in this browser only
Read Push Dominoes on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A row of tiles stands on edge and reads tiles. Each character is 'L' for a tile pushed leftwards at the same instant, 'R' for one pushed rightwards, and '.' for one left standing.

A falling tile pushes the standing tile beside it in the same direction, which then falls too, and so on. A standing tile pushed from both sides at the same instant stays standing. A tile already fallen is unaffected by anything that reaches it later.

Return the row once everything has settled.

Examples

Example 1

Input
tiles = "..R.."
Output
"..RRR"

The pushed tile topples everything to its right, one after another. The two standing tiles to its left have nothing pushing them at all.

Example 2

Input
tiles = "R.L"
Output
"R.L"

The middle tile is reached from both sides at the same instant, so it stays standing.

Example 3

Input
tiles = "L..R.."
Output
"L..RRR"

The leftward push at the front has nothing behind it to topple. The two standing tiles between the pushes are pushed apart rather than together, so neither falls. The rightward push topples everything after it.

Constraints

  • 1 <= tiles.length <= 10^5
  • Every character of tiles is 'L', 'R' or '.'.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def push_dominoes(tiles: str) -> str:
Java
public String pushDominoes(String tiles)

More on the same topics