algoadvance

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

• dominoes[i] = 'L' represents a domino that has been pushed to the left,
• dominoes[i] = 'R' represents a domino that has been pushed to the right, and
• dominoes[i] = '.' represents a domino that is standing still.

Return a string representing the final state.

Clarifying Questions

1. Q: What is the maximum length of the string?
   • A: The length of the string dominoes can be up to 100,000.
2. Q: Are there any invalid cases where dominoes could be pushed in both directions (like ‘R’ followed directly by ‘L’)?
   • A: Yes, such cases are valid and should be handled appropriately.
3. Q: Are there any constraints on the characters in the string?
   • A: The string will only contain the characters ‘L’, ‘R’, and ‘.’.

Strategy

1. Initial Setup:
   • Parse the initial state of the dominos string.
2. Double Pointer Approach:
   • Use two pointers (left and right) to find segments of dominos influenced by ‘R’ and ‘L’.
   • Traverse the string once and adjust the dominos according to the following rules:
     • For segments with ‘R’…’.’ (we change the ‘.’ into ‘R’).
     • For segments with ‘.’…‘L’ (we change the ‘.’ into ‘L’).
     • For segments with ‘R’…’.’…‘L’, balance dominos based on their distance from ‘R’ and ‘L’.
3. Construct Result:
   • Create a list to store the result as transformations are made and then convert it back to a string.

Code

def pushDominos(dominoes: str) -> str:
    n = len(dominoes)
    symbols = list(dominoes)
    forces = [0] * n
    
    # Scan left-to-right for 'R' forces
    force = 0
    for i in range(n):
        if symbols[i] == 'R':
            force = n
        elif symbols[i] == 'L':
            force = 0
        else:
            force = max(force - 1, 0)
        forces[i] += force
    
    # Scan right-to-left for 'L' forces
    force = 0
    for i in range(n-1, -1, -1):
        if symbols[i] == 'L':
            force = n
        elif symbols[i] == 'R':
            force = 0
        else:
            force = max(force - 1, 0)
        forces[i] -= force

    # Determine the final state
    result = []
    for f in forces:
        if f > 0:
            result.append('R')
        elif f < 0:
            result.append('L')
        else:
            result.append('.')
    
    return "".join(result)

# Example usage
dominoes = "RR.L"
print(pushDominos(dominoes))  # Output: "RR.L"

Time Complexity

• Time Complexity: O(n), where n is the length of the dominoes string. Each pass (left-to-right and right-to-left) takes linear time.
• Space Complexity: O(n), where n is used for the forces array and symbol list, both of which store intermediate states.

This solution ensures all dominos are properly accounted for within linear scanning, making it efficient for the input constraints.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?