Count Collisions on a Road — Medium Problem & Solution

Problem statement

Cars stand on an infinite road. directions[i] is 'L', 'R' or 'S' — moving left, moving right, or staying still.

When two moving cars meet head-on, both stop and that counts as two collisions. When a moving car hits a stationary one, it stops and that counts as one collision. Return the total number of collisions.

Example 1

Input: directions = "RLRSLL"
Output: 5
Explanation: Every car except the ones that escape ends up stopped.

Example 2

Input: directions = "LLRR"
Output: 0
Explanation: The left-movers drive away leftwards and the right-movers rightwards.

Example 3

Input: directions = "SSRSSRLLRSLLRSRSSRLRRRRLLRRLSSRR"
Output: 20

Constraints

• 1 <= directions.length <= 100000
• directions[i] is 'L', 'R' or 'S'

How to solve Count Collisions on a Road

Only the cars that can escape avoid a collision: a prefix of left-movers and a suffix of right-movers. Everything else is trapped, and each trapped moving car stops exactly once — contributing one collision apiece.

Approach

1. Advance i past the leading 'L' characters.
2. Retreat j past the trailing 'R' characters.
3. Count the characters in [i, j] that are not 'S'.

Why it works

Inside the trapped region there is a stationary car or an opposing car in both directions, so every moving car there must eventually stop — and the problem's scoring gives one collision per car that stops, whether it stopped against a moving or a stationary car. Cars that already stand still never move and so never collide.

Complexity

• Time — O(n)
• Space — O(1)

Pitfalls

• Counting each head-on meeting as one collision halves the answer — it is two, one per car.
• Only the leading 'L' run and trailing 'R' run escape; an 'L' in the middle is trapped.
• Stationary cars inside the region contribute nothing.

Reference solution

Python

def countCollisions(directions: str) -> int:
    n = len(directions)
    i, j = 0, n - 1
    while i < n and directions[i] == "L":
        i += 1
    while j >= 0 and directions[j] == "R":
        j -= 1
    return sum(1 for k in range(i, j + 1) if directions[k] != "S")

JavaScript

var countCollisions = function(directions) {
    var n = directions.length;
    var i = 0, j = n - 1;
    while (i < n && directions.charAt(i) === "L") i++;
    while (j >= 0 && directions.charAt(j) === "R") j--;
    var count = 0;
    for (var k = i; k <= j; k++) if (directions.charAt(k) !== "S") count++;
    return count;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Make Three Strings Equal Medium
• Number of Ways to Divide a Long Corridor Medium
• Maximum Number of Non-overlapping Palindrome Substrings Medium
• Count Number of Texts Medium
• Delete Characters to Make Fancy String Medium
• Count Number of Homogenous Substrings Medium