Problem Description

You have n cars positioned on an infinitely long road, numbered from 0 to n - 1 from left to right. Each car occupies a unique position on the road.

You're given a string directions of length n where each character represents a car's movement:

• 'L' means the car is moving left
• 'R' means the car is moving right
• 'S' means the car is stationary (not moving)

All moving cars travel at the same speed.

When cars collide, the collision count increases based on these rules:

• When two cars moving in opposite directions collide (one going left, one going right), the collision count increases by 2
• When a moving car collides with a stationary car, the collision count increases by 1

After any collision, the cars involved stop moving and remain at the collision point. Cars cannot change their direction or state except when colliding.

Your task is to calculate the total number of collisions that will occur.

The key insight is that cars moving left at the beginning ('L') will never collide with anything since there's nothing to their left. Similarly, cars moving right at the end ('R') will never collide since there's nothing to their right. Therefore, we can ignore the prefix of 'L' characters and suffix of 'R' characters.

For the remaining middle portion, any car that isn't stationary ('S') will eventually collide and contribute to the collision count. Each non-'S' character in this middle portion contributes exactly 1 to the total collision count, as each represents one car that will stop due to a collision.

The solution strips the irrelevant prefix 'L' and suffix 'R', then counts all non-'S' characters in the remaining string, which equals the total length minus the count of 'S' characters.

Intuition

Let's think about what happens to each car step by step.

First, consider the cars at the boundaries. Cars moving left at the leftmost positions will just keep going left forever without hitting anything. Similarly, cars moving right at the rightmost positions will keep going right forever. These cars will never contribute to any collisions.

Now, what about the cars in between? Let's trace through what happens:

1. If a car is moving right ('R') and encounters a stationary car ('S') or a car moving left ('L'), it will collide and stop.
2. If a car is moving left ('L') and encounters a stationary car ('S') or a car moving right ('R'), it will collide and stop.
3. Once any collision happens, the colliding cars become stationary, creating a "wall" that other moving cars will eventually hit.

The key realization is that once we remove the cars that escape (prefix 'L' and suffix 'R'), every remaining moving car MUST eventually collide with something. Why? Because:

• A car moving right will either hit another car directly or hit a "wall" of stopped cars
• A car moving left will either hit another car directly or hit a "wall" of stopped cars
• The collision creates a chain reaction where stopped cars act as barriers for other moving cars

Each moving car that collides contributes exactly 1 to our answer when it stops. It doesn't matter if two cars collide head-on (contributing 2 total) or if one car hits a stationary car (contributing 1) - in both cases, each moving car that stops adds exactly 1 to our count.

Therefore, the answer is simply the count of all moving cars that will eventually stop, which is all the 'L' and 'R' characters in the middle section (after removing the escaping prefix and suffix). This equals len(middle_section) - count('S').

Learn more about Stack patterns.

Solution Approach

The implementation is remarkably elegant once we understand the intuition. Here's how we translate our understanding into code:

Step 1: Remove cars that will never collide

We use Python's string methods to strip away the cars that escape:

• lstrip("L") removes all consecutive 'L' characters from the beginning of the string
• rstrip("R") removes all consecutive 'R' characters from the end of the string

For example, if directions = "LLRRLSSRL":

• After lstrip("L"): "RRLSSRL"
• After rstrip("R"): "RRLSSR"

This gives us s = directions.lstrip("L").rstrip("R"), which contains only the cars that might participate in collisions.

Step 2: Count the moving cars that will collide

In the remaining string s, every car that isn't stationary will eventually collide and stop. We need to count:

• All 'L' characters (cars moving left that will hit something)
• All 'R' characters (cars moving right that will hit something)

This is equivalent to counting all non-'S' characters in s.

The count can be calculated as: total_cars - stationary_cars = len(s) - s.count("S")

Complete Solution:

class Solution:
    def countCollisions(self, directions: str) -> int:
        s = directions.lstrip("L").rstrip("R")
        return len(s) - s.count("S")

Time Complexity: O(n) where n is the length of the directions string. We traverse the string a constant number of times for the strip operations and counting.

Space Complexity: O(1) as we only use a constant amount of extra space (the stripped string reuses the original string's memory in Python).

The beauty of this solution lies in recognizing that we don't need to simulate the actual collisions - we just need to identify which cars will eventually stop, turning a potentially complex simulation problem into a simple counting problem.

Example Walkthrough

Let's trace through a concrete example to see how the solution works.

Example: directions = "LLRSSRL"

Step 1: Identify cars that will never collide

First, let's visualize the initial setup with 7 cars (indexed 0-6):

Position: 0  1  2  3  4  5  6
Car:      L  L  R  S  S  R  L
Motion:   ←  ←  →  -  -  →  ←

The leftmost cars (positions 0 and 1) are moving left (L). Since there's nothing to their left, they'll escape forever without hitting anything.

The rightmost car (position 6) is moving left (L), so it might collide with something to its left.

Step 2: Strip the escaping cars

• Remove prefix Ls: "LLRSSRL" → "RSSRL"
• Remove suffix Rs: "RSSRL" → "RSSRL" (no trailing Rs to remove)

So our trimmed string is s = "RSSRL"

Step 3: Count collisions

In the trimmed string "RSSRL", we have:

• Position 0: R (moving right) - will eventually hit the stationary car at position 1
• Position 1: S (stationary) - already stopped, won't contribute
• Position 2: S (stationary) - already stopped, won't contribute
• Position 3: R (moving right) - will eventually hit the car moving left at position 4
• Position 4: L (moving left) - will collide head-on with the car at position 3

Every moving car (R or L) in this trimmed section will eventually stop due to a collision:

• The first R hits the stationary car S → contributes 1
• The second R and the L collide head-on → each contributes 1 (total 2)

Total moving cars that will collide = Total cars - Stationary cars = len("RSSRL") - count('S') = 5 - 2 = 3

Therefore, the answer is 3.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the length of the string directions.

The time complexity breaks down as follows:

• lstrip("L"): O(n) in the worst case when all characters are "L"
• rstrip("R"): O(n) in the worst case when all remaining characters are "R"
• len(s): O(1) operation
• s.count("S"): O(n) as it needs to traverse the entire string s

Since these operations are performed sequentially, the overall time complexity is O(n) + O(n) + O(1) + O(n) = O(n).

Space Complexity: O(n) or O(1), depending on the Python implementation.

The space complexity analysis:

• In Python, strings are immutable, so lstrip() and rstrip() create new string objects. This results in O(n) space complexity as a new string s is created.
• However, if we consider only the additional space used by the algorithm (not counting the space for the output), the space complexity could be considered O(1) since no additional data structures proportional to the input size are used beyond the string manipulation.

The reference answer mentions both O(n) and O(1) because it depends on whether we count the space used for creating the intermediate string s or only the auxiliary space used by the algorithm.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Misunderstanding the Collision Count Rules

The Mistake: A common error is thinking that each collision between two moving cars contributes 1 to the count, not 2. This leads to incorrect calculations where developers might try to count pairs of colliding cars differently.

Why It Happens: The problem states that when two cars moving in opposite directions collide, the count increases by 2. Some might interpret this as "one collision = 1 count" and miss the special case.

The Reality: The solution works because it counts each car that stops, not each collision event. When two moving cars collide (R meets L), both cars stop, contributing 2 to the count (1 for each car). When a moving car hits a stationary one, only the moving car stops, contributing 1.

Example:

• "RL" → Both cars stop → Count = 2
• "RS" → Only R stops → Count = 1
• "SL" → Only L stops → Count = 1

Pitfall 2: Attempting to Simulate Actual Collisions

The Mistake: Trying to track car positions and simulate movement step-by-step, checking for collisions at each time unit.

Why It Happens: The problem description naturally suggests a simulation approach, making it tempting to model cars moving along the road.

The Fix: Recognize that the final count only depends on which cars will eventually stop, not when or where they collide. Every non-stationary car in the "collision zone" (after removing escaping cars) will eventually stop.

Pitfall 3: Incorrectly Handling Edge Cases

The Mistake: Forgetting to handle strings that become empty after stripping, or strings containing only 'S' characters.

Example Cases:

• "LLL" → After stripping: "" → Count should be 0
• "RRR" → After stripping: "" → Count should be 0
• "SSS" → After stripping: "SSS" → Count should be 0

The Solution: The given code naturally handles these cases:

• Empty string after stripping: len("") - "".count("S") = 0 - 0 = 0
• Only stationary cars: len("SSS") - "SSS".count("S") = 3 - 3 = 0

Pitfall 4: Order of Stripping Operations

The Mistake: Applying rstrip("R") before lstrip("L") or trying to strip both simultaneously.

Why It Matters: While the order doesn't affect the final result for this problem, understanding the logic flow is important. We remove left-escaping cars first, then right-escaping cars from what remains.

Correct Approach:

# Correct: left first, then right
s = directions.lstrip("L").rstrip("R")

# Also correct but less intuitive:
s = directions.rstrip("R").lstrip("L")

# Incorrect attempt at simultaneous stripping:
# s = directions.strip("LR")  # This would remove L and R from both ends!

The strip("LR") would incorrectly remove any combination of 'L' and 'R' from both ends, which is not what we want.