Push dominoes

September 27, 2022

two-pointers

Problem URL: Push dominoes

Any triplet that reaches the state R.L remains that state permanently. These changes occur to pairs that are not part of an R.L, R. -> RR an .L -> LL. To avoid the problem with the R.L state when we address the R. -> RR and .L -> LL changes, we replace each R.L with a dummy string (say, xxx). Then we perform the R. -> RR, .L -> LL replacements. Once the described actions are complete and no other replacements are occured, we replace the dummy xxx string with R.L and return as result.

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

        while dominoes != temp:
            temp = dominoes
            dominoes = dominoes.replace('R.L', 'xxx')
            dominoes = dominoes.replace('R.', 'RR')
            dominoes = dominoes.replace('.L', 'LL')

        return  dominoes.replace('xxx', 'R.L')            

Time Complexity: O(n^2)
Space Complexity: O(1)