1
// Time complexity: O(N)
2
// Space complexity: O(N), where N is the length of input string
3
class Solution {
4
  public String pushDominoes(String dominoes) {
5
    // ask whether dominoes could be null
6
    final int N = dominoes.length();
7
    if (N <= 1) return dominoes;
8
    char[] res = dominoes.toCharArray();
9
    int i = 0;
10
    while (i < N) {
11
      if (res[i] == '.') {
12
        i++;
13
      } else if (res[i] == 'L') { // push left
14
        int j = i - 1;
15
        while (j >= 0 && res[j] == '.') {
16
          res[j--] = 'L';
17
        }
18
        i++;
19
      } else { // res[i] == 'R'
20
        int j = i + 1;
21
        while (j < N && res[j] == '.') { // try to find 'R' or 'L' in the right side
22
          j++;
23
        }
24
        if (j < N && res[j] == 'L') { // if found 'L', push left and right
25
          for (int l = i + 1, r = j - 1; l < r; l++, r--) {
26
            res[l] = 'R';
27
            res[r] = 'L';
28
          }
29
          i = j + 1;
30
        } else { // if no 'L', push right
31
          while (i < j) {
32
            res[i++] = 'R';
33
          }
34
        }
35
      }
36
    }
37
    return String.valueOf(res);
38
  }
39
}