There are N dominoes in a line, and we place each domino vertically upright.
In the beginning, we simultaneously push some of the dominoes either to the left or to the right.

After each second, each domino that is falling to the left pushes the adjacent domino on the left.
Similarly, the dominoes falling to the right push their adjacent dominoes standing on the right.
When a vertical domino has dominoes falling on it from both sides, it stays still due to the balance of the forces.
For the purposes of this question, we will consider that a falling domino expends no additional force to a falling or already fallen domino.
Given a string "S" representing the initial state. S[i] = 'L', if the i-th domino has been pushed to the left; S[i] = 'R', if the i-th domino has been pushed to the right; S[i] = '.', if the i-th domino has not been pushed.
Return a string representing the final state. 
Example 1:
Input: ".L.R...LR..L.."
Output: "LL.RR.LLRRLL.."

Example 2:
Input: "RR.L"
Output: "RR.L"
Explanation: The first domino expends no additional force on the second domino.

Note:

0 <= N <= 10^5
String dominoes contains only 'L', 'R' and '.'

Difficulty: interview

Starter code:

class Solution:
    def pushDominoes(self, dominoes: str) -> str:
        

Solutions:
INF = float('inf')
class Solution:
    def pushDominoes(self, dominoes: str) -> str:
        n = len(dominoes)
        d1 = [-1] * n
        d2 = [-1] * n
        
        cnt = INF
        for i in range(n - 1, -1, -1):
            if dominoes[i] == 'L':
                cnt = 0
            elif dominoes[i] == '.':
                cnt += 1
            elif dominoes[i] == 'R':
                cnt = INF
            d1[i] = cnt
        
        cnt = INF
        for i in range(n):
            if dominoes[i] == 'R':
                cnt = 0
            elif dominoes[i] == '.':
                cnt += 1
            elif dominoes[i] == 'L':
                cnt = INF
            d2[i] = cnt
    
        ret = []
        for i in range(n):
            if d1[i] == d2[i]:
                ret.append('.')
            elif d1[i] < d2[i]:
                ret.append('L')
            else:
                ret.append('R')
        return ''.join(ret)

class Solution:
    def pushDominoes(self, dominoes: str) -> str:
        n = len(dominoes)
        
        d = [0] * n
        
        force = 0
        
        for i in range(n):
            c = dominoes[i]
            
            if c == 'R':
                force = n
            elif c == 'L':
                force = 0
            else:
                force = max(force - 1, 0)
                
            d[i] += force
            
        force = 0
        
        for i in range(n-1, -1, -1):
            c = dominoes[i]
            
            if c == 'R':
                force = 0
            elif c == 'L':
                force = n
            else:
                force = max(force - 1, 0)
                
            d[i] -= force
            
        def inner():
            for f in d:
                if f == 0:
                    yield '.'
                elif f > 0:
                    yield 'R'
                else:
                    yield 'L'
                    
        return ''.join(inner())

class Solution:
    def pushDominoes(self, dominoes: str) -> str:
        n = len(dominoes)
        force = [0] * n
        f = 0
        for i in range(n):
            if dominoes[i] == 'R':
                f = n
            elif dominoes[i] == 'L':
                f = 0
            else:
                f = max(f-1, 0)
            force[i] += f
        for i in range(n-1, -1, -1):
            if dominoes[i] == 'L':
                f = n
            elif dominoes[i] == 'R':
                f = 0
            else:
                f = max(f-1, 0)
            force[i] -= f
        return ''.join('.' if f==0 else 'R' if f > 0 else 'L' for f in force)

class Solution:
    def pushDominoes(self, dominoes: str) -> str:
        l = len(dominoes)
        right_force = [0]*l
        left_force = [0]*l
        force1 = 0
        force2 = 0
        for i in range(l):
            if dominoes[i]=='R':
                force1 = l
            elif dominoes[i]=='L':
                force1 = 0
            else:
                force1 = max(force1 - 1, 0)
            right_force[i] += force1
        for i in range(l-1, -1, -1):
            if dominoes[i]=='L':
                force2 = l
            elif dominoes[i]=='R':
                force2 = 0
            else:
                force2 = max(force2 - 1, 0)
            left_force[i] += force2

        result = ''
        for i in range(l):
            if right_force[i] > left_force[i]:
                result += 'R'
            elif right_force[i] < left_force[i]:
                result += 'L'
            else:
                result += '.'
        return result

class Solution:
    def pushDominoes(self, dominoes: str) -> str:
        forces = [0] * len(dominoes)
        max_force = len(dominoes)

        force = 0
        for i, d in enumerate(dominoes):
            if d == 'R':
                force = max_force
            elif d == 'L': # have to use elif here, not if
                force = 0
            else:
                force = max(0, force - 1)
            forces[i] += force

        force = 0
        for i in range(len(dominoes) - 1, -1, -1):
            d = dominoes[i]
            if d == 'L':
                force = max_force
            elif d == 'R':
                force = 0
            else:
                force = max(0, force - 1)
            forces[i] -= force
            
        print(forces)

        result = ''
        for f in forces:
            if f == 0:
                result += '.'
            elif f > 0:
                result += 'R'
            else:
                result += 'L'
        return result
    
# TC: O(N)
# SC: O(N)


class Solution:
    def pushDominoes(self, dominoes: str) -> str:
        n = len(dominoes)
        balance = [0] * len(dominoes)
        
        b = 0
        for index,c in enumerate(dominoes):
            if c == 'R':
                b = n
            elif c == 'L':
                b = 0
            else:
                b = max(b - 1, 0)
            balance[index] += b

        b = 0
        for index,c in enumerate(reversed(dominoes)):
            index = -index - 1
            if c == 'R':
                b = 0
            elif c == 'L':
                b = n
            else:
                b = max(b - 1, 0)
            balance[index] -= b

        result = ['.'] * len(dominoes)
        for i in range(len(dominoes)):
            if dominoes[i] == 'R' or dominoes[i] == 'L':
                result[i] = dominoes[i]
            elif balance[i] > 0:
                result[i] = 'R'
            elif balance[i] < 0:
                result[i] = 'L'
        return ''.join(result)