Push Dominoes

medium string two-pointers simulation

Problem

A row of dominoes contains 'L', 'R', or '.'. Each second, an upright domino falls in the direction of an adjacent pushed one. If both directions push it simultaneously, it stays upright. Return the final state.

Inputdominoes = ".L.R...LR..L.."

Output"LL.RR.LLRRLL.."

Forces from L and R propagate symmetrically.

dominoes (L, R, or .)

def pushDominoes(d):
    s = "L" + d + "R"
    res = []
    prev = 0
    for i in range(1, len(s)):
        if s[i] == ".": continue
        mid = i - prev - 1
        if s[prev] == s[i]:
            res.append(s[i] * mid)
        elif s[prev] == "L" and s[i] == "R":
            res.append("." * mid)
        else:
            res.append("R" * (mid // 2) + ("." if mid % 2 else "") + "L" * (mid // 2))
        if i < len(s) - 1:
            res.append(s[i])
        prev = i
    return "".join(res)

function pushDominoes(d) {
  const s = "L" + d + "R";
  const parts = [];
  let prev = 0;
  for (let i = 1; i < s.length; i++) {
    if (s[i] === ".") continue;
    const mid = i - prev - 1;
    if (s[prev] === s[i]) parts.push(s[i].repeat(mid));
    else if (s[prev] === "L" && s[i] === "R") parts.push(".".repeat(mid));
    else parts.push("R".repeat(mid >> 1) + (mid % 2 ? "." : "") + "L".repeat(mid >> 1));
    if (i < s.length - 1) parts.push(s[i]);
    prev = i;
  }
  return parts.join("");
}

class Solution {
  public String pushDominoes(String d) {
    String s = "L" + d + "R";
    StringBuilder sb = new StringBuilder();
    int prev = 0;
    for (int i = 1; i < s.length(); i++) {
      if (s.charAt(i) == '.') continue;
      int mid = i - prev - 1;
      char a = s.charAt(prev), b = s.charAt(i);
      if (a == b) for (int k = 0; k < mid; k++) sb.append(a);
      else if (a == 'L' && b == 'R') for (int k = 0; k < mid; k++) sb.append('.');
      else { for (int k = 0; k < mid / 2; k++) sb.append('R'); if (mid % 2 == 1) sb.append('.'); for (int k = 0; k < mid / 2; k++) sb.append('L'); }
      if (i < s.length() - 1) sb.append(b);
      prev = i;
    }
    return sb.toString();
  }
}

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    string pushDominoes(string d) {
        string s = "L" + d + "R";
        string out;
        int prev = 0;
        for (int i = 1; i < (int)s.size(); i++) {
            if (s[i] == '.') continue;
            int mid = i - prev - 1;
            char a = s[prev], b = s[i];
            if (a == b) out += string(mid, a);
            else if (a == 'L' && b == 'R') out += string(mid, '.');
            else out += string(mid / 2, 'R') + string(mid % 2, '.') + string(mid / 2, 'L');
            if (i < (int)s.size() - 1) out += b;
            prev = i;
        }
        return out;
    }
};

Explanation

Instead of simulating second-by-second, we notice that the final picture is decided entirely by each pair of neighboring pushed dominoes (the Ls and Rs) and the dots between them. So we look at consecutive non-dot characters and fill the gap between them.

To handle the ends cleanly, we pad the string: a virtual "L" on the left and "R" on the right, so every real domino has a force on both sides. We track prev (the last pushed domino) and walk forward to the next one at index i, with mid dots in between.

Four gap cases. If both sides push the same way (L..L or R..R), all dots fall that way. If it is R..L, the forces meet, so dots split: left half becomes R, right half becomes L, and a lone middle dot (odd gap) stays upright. If it is L..R, the forces pull apart and the dots stay as ..

After resolving each gap we also append the pushed character itself, then advance prev to i.

Example: in ".L.R...LR..L..", the segment between an R and an L with 3 dots becomes "R.L", while a segment between two same-direction forces fills entirely — producing "LL.RR.LLRRLL..".

Time: O(n) Space: O(n)