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.

You are given a string dominoes representing the initial state where:


	dominoes[i] = 'L', if the ith domino has been pushed to the left,
	dominoes[i] = 'R', if the ith domino has been pushed to the right, and
	dominoes[i] = '.', if the ith domino has not been pushed.


Return a string representing the final state.

&nbsp;
Example 1:

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


Example 2:

Input: dominoes = ".L.R...LR..L.."
Output: "LL.RR.LLRRLL.."


&nbsp;
Constraints:


	n == dominoes.length
	1 &lt;= n &lt;= 105
	dominoes[i] is either 'L', 'R', or '.'.


class Solution:
    def pushDominoes(self, dom: str) -> str:
        from collections import deque
        n = len(dom)
        d = set()
        q = deque()
        arr = [0 for i in range(n)]
        for i in range(n):
            if dom[i] == "L":
                arr[i] = -1
                d.add(i)
                q.append((i,"L"))
            if dom[i] == "R":
                arr[i] = 1
                d.add(i)
                q.append((i,"R"))
        while q:
            t1 = set()
            for _ in range(len(q)):
                t = q.popleft()
                if t[1] == "L":
                    if t[0]-1 >= 0 and t[0]-1 not in d:
                        t1.add(t[0]-1)
                        arr[t[0]-1] -= 1
                else:
                    if t[0]+1 < n and t[0]+1 not in d:
                        t1.add(t[0]+1)
                        arr[t[0]+1] += 1
            for val in t1:
                d.add(val)
                if arr[val] > 0:
                    q.append((val,"R"))
                elif arr[val]<0:
                    q.append((val,"L"))
        ans = ""
        for val in arr:
            if val<0:
                ans += "L"
            elif val>0:
                ans += "R"
            else:
                ans += "."
        return ans
// Time complexity: O(N)
// Space complexity: O(N), where N is the length of input string
class Solution {
    public String pushDominoes(String dominoes) {
        // ask whether dominoes could be null
        final int N = dominoes.length();
        if (N <= 1) return dominoes;
        char[] res = dominoes.toCharArray();
        int i = 0;
        while (i < N) {
            if (res[i] == '.') {
                i++;
            } else if (res[i] == 'L') { // push left
                int j = i-1;
                while (j >= 0 && res[j] == '.') {
                    res[j--] = 'L';
                }
                i++;
            } else { // res[i] == 'R'
                int j = i+1;
                while (j < N && res[j] == '.') { // try to find 'R' or 'L' in the right side
                    j++;
                }
                if (j < N && res[j] == 'L') { // if found 'L', push left and right
                    for (int l = i+1, r = j-1; l < r; l++, r--) {
                        res[l] = 'R';
                        res[r] = 'L';
                    }
                    i = j + 1;
                } else { // if no 'L', push right
                    while (i < j) {
                        res[i++] = 'R';
                    }
                }
            }
        }
        return String.valueOf(res);
    }
}
class Solution {
public:
    string pushDominoes(string dominoes) {
        #define SET(ch, arr) \
                    if (dominoes[i] == ch) { count = 1; prev = ch; } \
                    else if (dominoes[i] != '.') prev = dominoes[i]; \
                    if (prev == ch && dominoes[i] == '.') arr[i] = count++;

        string res = "";
        char prev;
        int n = dominoes.size(), count = 1;

        vector<int> left(n, 0), right(n, 0);
        for (int i = 0; i < n; i++) {
            SET('R', right);
        }

        prev = '.';
        for (int i = n-1; i >= 0; i--) {
            SET('L', left);
        }

        for (int i = 0; i < n; i++) {
            if (!left[i] && !right[i]) res += dominoes[i];
            else if (!left[i]) res += 'R';
            else if (!right[i]) res += 'L';
            else if (left[i] == right[i]) res += '.';
            else if (left[i] < right[i]) res += 'L';
            else res += 'R';
        }

        return res;
    }
};
/**
 * @param {string} dominoes
 * @return {string}
 */
var pushDominoes = function(dominoes) {
    
    let len = dominoes.length;
    let fall = [];
    let force = 0;
    let answer = "";
    
    // Traverse from left to right. Focus on the dominoes falling to the right
    for (let i = 0; i < len; i++) {
        if (dominoes[i] == 'R') {
            force = len;
        } else if (dominoes[i] == 'L') {
            force = 0;
        } else {
            force = Math.max(force-1,0);
        }
        fall[i] = force;
    }
    
    //console.log('fall array 1: ', fall);
    
    // Traverse from right to left. Focus on the dominoes falling to the left
    // Subtract the value from the values above
    for (let i = len-1; i >= 0; i--) {
        if (dominoes[i] == 'L') {
            force = len;
        } else if (dominoes[i] == 'R') {
            force = 0;
        } else {
            force = Math.max(force-1,0);
        }
        fall[i] -= force;
    }    
    
    //console.log('fall array 2: ', fall);
    
    // Just traverse through the fall[] array and assign the values in the answer string accordingly
    for (let i = 0; i < len; i++) {
        if (fall[i] < 0)
            answer += 'L';
        else if (fall[i] > 0 )
            answer += 'R';
        else
            answer += '.';
    }
    
    //console.log('answer: ', answer);
    
    return answer;
    
};
Push Dominoes