Problem statement

https://leetcode.com/problems/push-dominoes/

Solution

Let us iterate through our string and keep two pointers: for positions where values not equal to . and the go one after another. Pointers prev, i can point to symbols L or R and we can have 4 different options:

  1. L...L, in this case, we need to fill everything with L
  2. R...R, in this case, we need to fill everything with R
  3. L...R, we need to keep it as it is
  4. R...L, then we need to fill first half with R and second with L, handling odd and even cases.

Complexity

Time complexity is O(n), space is O(n) as well.

Code

class Solution:
    def pushDominoes(self, D):
        D = "L" + D + "R"
        n, prev, ans = len(D), 0, ""
        for i in range(1, n):
            diff = i - prev - 1
            if D[i] == ".": continue
            
            if D[i] == D[prev]:
                ans += D[i]*diff     
            elif D[i] == "L" and D[prev] == "R":
                m, d = divmod(diff, 2)
                ans += "R"*m + "."*d + "L"*m
            else:
                ans += "."*diff
                
            ans += D[i]
            prev = i
        
        return ans[:-1]