Count Collisions on a Road

Problem

There are n cars on an infinitely long road. The cars are numbered from 0 to n - 1 from left to right and each car is present at a unique point.

You are given a 0-indexed string directions of length n. directions[i] can be either 'L', 'R', or 'S' denoting whether the ith car is moving towards the left , towards the right , or staying at its current point respectively. Each moving car has the same speed.

The number of collisions can be calculated as follows:

When two cars moving in opposite directions collide with each other, the number of collisions increases by 2.
When a moving car collides with a stationary car, the number of collisions increases by 1.

After a collision, the cars involved can no longer move and will stay at the point where they collided. Other than that, cars cannot change their state or direction of motion.

Return thetotal number of collisions that will happen on the road.

Examples

Example 1

1
2
3
4
5
6
7
8
9


Input: directions = "RLRSLL"
Output: 5
Explanation:
The collisions that will happen on the road are:
- Cars 0 and 1 will collide with each other. Since they are moving in opposite directions, the number of collisions becomes 0 + 2 = 2.
- Cars 2 and 3 will collide with each other. Since car 3 is stationary, the number of collisions becomes 2 + 1 = 3.
- Cars 3 and 4 will collide with each other. Since car 3 is stationary, the number of collisions becomes 3 + 1 = 4.
- Cars 4 and 5 will collide with each other. After car 4 collides with car 3, it will stay at the point of collision and get hit by car 5. The number of collisions becomes 4 + 1 = 5.
Thus, the total number of collisions that will happen on the road is 5. 

Example 2

1
2
3
4


Input: directions = "LLRR"
Output: 0
Explanation:
No cars will collide with each other. Thus, the total number of collisions that will happen on the road is 0.

Constraints

1 <= directions.length <= 10^5
directions[i] is either 'L', 'R', or 'S'.

Solution

Method 1 – Greedy Simulation with Trimming

Intuition

Cars moving left at the very start and cars moving right at the very end will never collide with anyone, as there are no cars in their path. All other moving cars will eventually collide with something (either a stationary car or a car moving in the opposite direction). So, we can trim the leading ‘L’s and trailing ‘R’s, and count all remaining moving cars (‘R’ or ‘L’) as collisions.

Approach

Find the first index from the left that is not ‘L’ (let’s call it l).
Find the last index from the right that is not ‘R’ (let’s call it r).
For the substring between l and r (inclusive), count the number of ‘L’ and ‘R’ (each will cause a collision).
Return this count.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


class Solution {
public:
    int countCollisions(string dirs) {
        int n = dirs.size(), ans = 0, l = 0, r = n - 1;
        while (l < n && dirs[l] == 'L') l++;
        while (r >= 0 && dirs[r] == 'R') r--;
        for (int i = l; i <= r; ++i)
            if (dirs[i] != 'S') ans++;
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


func countCollisions(dirs string) int {
    n := len(dirs)
    l, r := 0, n-1
    for l < n && dirs[l] == 'L' {
        l++
    }
    for r >= 0 && dirs[r] == 'R' {
        r--
    }
    ans := 0
    for i := l; i <= r; i++ {
        if dirs[i] != 'S' {
            ans++
        }
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


class Solution {
    public int countCollisions(String dirs) {
        int n = dirs.length(), l = 0, r = n - 1, ans = 0;
        while (l < n && dirs.charAt(l) == 'L') l++;
        while (r >= 0 && dirs.charAt(r) == 'R') r--;
        for (int i = l; i <= r; i++)
            if (dirs.charAt(i) != 'S') ans++;
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


class Solution {
    fun countCollisions(dirs: String): Int {
        var l = 0
        var r = dirs.length - 1
        while (l < dirs.length && dirs[l] == 'L') l++
        while (r >= 0 && dirs[r] == 'R') r--
        var ans = 0
        for (i in l..r) {
            if (dirs[i] != 'S') ans++
        }
        return ans
    }
}

1
2
3
4
5
6
7
8


class Solution:
    def countCollisions(self, dirs: str) -> int:
        l, r = 0, len(dirs) - 1
        while l < len(dirs) and dirs[l] == 'L':
            l += 1
        while r >= 0 and dirs[r] == 'R':
            r -= 1
        return sum(1 for i in range(l, r + 1) if dirs[i] != 'S')

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


impl Solution {
    pub fn count_collisions(dirs: String) -> i32 {
        let bytes = dirs.as_bytes();
        let n = bytes.len();
        let mut l = 0;
        let mut r = n as i32 - 1;
        while l < n && bytes[l] == b'L' { l += 1; }
        while r >= 0 && bytes[r as usize] == b'R' { r -= 1; }
        let mut ans = 0;
        for i in l..=r as usize {
            if bytes[i] != b'S' { ans += 1; }
        }
        ans
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


class Solution {
    countCollisions(dirs: string): number {
        let l = 0, r = dirs.length - 1;
        while (l < dirs.length && dirs[l] === 'L') l++;
        while (r >= 0 && dirs[r] === 'R') r--;
        let ans = 0;
        for (let i = l; i <= r; i++) {
            if (dirs[i] !== 'S') ans++;
        }
        return ans;
    }
}

Complexity

⏰ Time complexity: O(n), as we scan the string at most twice.
🧺 Space complexity: O(1), only a few variables are used.

Problem#

Examples#

Example 1#

Example 2#

Constraints#

Solution#

Method 1 – Greedy Simulation with Trimming#

Intuition#

Approach#

Code#

Complexity#