Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Cars moving left at the far left and cars moving right at the far right escape without collision. Every moving car between those escaping prefixes and suffixes eventually stops in a collision, contributing one to the count; a head-on collision contributes two because two moving cars stop. Already stationary cars contribute nothing themselves.

Approach

Find the first position that is not L and the last that is not R. Return zero if no retained interval exists. Count stationary cars inside that interval and subtract them from its length. The remaining positions are precisely the moving cars that collide. This counts collision contributions without simulating timing or individual collision chains.

class Solution:
    def countCollisions(self, directions: str) -> int:
        l, r = -1, -1
        s = 0
        n = len(directions)

        for i in range(n):
            if directions[i] in ['R', 'S']:
                l = i
                break

        for i in range(n - 1, -1, -1):
            if directions[i] in ['L', 'S']:
                r = i
                break

        if l == -1 or r == -1 or l > r:
            return 0

        for i in range(l, r + 1):
            if directions[i] == 'S':
                s += 1
        return r - l - s + 1

Complexity analysis

Let n = directions.length. Time: O(n) across the boundary and stationary-car scans. Auxiliary space: O(1).