Count Collisions on a Road

Problem Description

Given a string representing the directions of cars on an infinitely long road, determine the total number of collisions that will happen as the cars move. Each car can be moving left ('L'), right ('R'), or stationary ('S'). The collisions occur between two cars moving in opposite directions or a moving car colliding with a stationary car.

Key Insights

• A collision between two cars moving towards each other ('R' and 'L') counts as 2 collisions.
• A collision between a moving car and a stationary car ('S') counts as 1 collision.
• Once a collision occurs, the involved cars become stationary and do not contribute to further collisions.
• The problem can be solved by iterating through the string and counting collisions based on the adjacent car directions.

Space and Time Complexity

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

Solution

To solve the problem, we can iterate through the string of directions and keep track of the collision counts. We need to look for specific patterns in the string:

1. When encountering 'R' followed by 'L', we increment the collision count by 2.
2. When encountering 'R' followed by 'S', we increment the collision count by 1.
3. When encountering 'S' followed by 'L', we increment the collision count by 1.
4. We must also ensure that after a collision, the involved cars are treated as stationary for subsequent checks.

We can achieve this using a simple loop to traverse the string while applying the above rules.

Code Solutions