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

<p>You are given a <strong>0-indexed</strong> string <code>directions</code> of length <code>n</code>. <code>directions[i]</code> can be either <code>&#39;L&#39;</code>, <code>&#39;R&#39;</code>, or <code>&#39;S&#39;</code> denoting whether the <code>i<sup>th</sup></code> car is moving towards the <strong>left</strong>, towards the <strong>right</strong>, or <strong>staying</strong> at its current point respectively. Each moving car has the <strong>same speed</strong>.</p>

<p>The number of collisions can be calculated as follows:</p>

<ul>
	<li>When two cars moving in <strong>opposite</strong> directions collide with each other, the number of collisions increases by <code>2</code>.</li>
	<li>When a moving car collides with a stationary car, the number of collisions increases by <code>1</code>.</li>
</ul>

<p>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.</p>

<p>Return <em>the <strong>total number of collisions</strong> that will happen on the road</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> directions = &quot;RLRSLL&quot;
<strong>Output:</strong> 5
<strong>Explanation:</strong>
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. 
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> directions = &quot;LLRR&quot;
<strong>Output:</strong> 0
<strong>Explanation:</strong>
No cars will collide with each other. Thus, the total number of collisions that will happen on the road is 0.</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= directions.length &lt;= 10<sup>5</sup></code></li>
	<li><code>directions[i]</code> is either <code>&#39;L&#39;</code>, <code>&#39;R&#39;</code>, or <code>&#39;S&#39;</code>.</li>
</ul>

class Solution:
    def countCollisions(self, directions: str) -> int:
        # Two cars can't move past each other so the order is
        # the same.  Represent the state by an array "directions"
        # representing current direction of travel for each car.
        #
        # I just noticed something (thanks to test case 115):  If
        # we have a bunch of R's, say "nr" followed by an L, what's going
        # to happen is one RL worth 2 collisions, plus the number
        # of RS worth 1 collision each or nr-1+2 or a total of nr+1.
        # If the nr R's are followed by nl L's, then I think the result
        # is nr + 1 + nl - 1 for a total of nr + nl.  If we have nr R's
        # followed by 1 or more S's, we will end up with a total of nr.
        # In the general case, these agglomerations may help a little
        # with processing and the preprocessing into runs should't be
        # very expensive (O(n)).
        n_collisions = 0   # Remember each -><- is worth one or two collisions
        direction_runs = self.generate_runs( directions )
        prev_run = next( direction_runs )
        for direction_run in direction_runs:
            left_direction, left_count = prev_run
            right_direction, right_count = direction_run
            # Case 1:  bunch of R's -> bunch of <- L's => nr + nl + 1
            if left_direction == 'R' and right_direction == 'L':
                n_collisions += left_count + right_count
            elif left_direction == 'R' and right_direction == 'S':
                n_collisions += left_count
            elif left_direction == 'S' and right_direction == 'L':
                n_collisions += right_count
            prev_run = direction_run
        return n_collisions

    # Generates, via "yield", the succession of same-valued runs represented
    # by 2-tuples (value, count); similar to output for Counter except that
    # there, the count is over all instances whereas this generates counts
    # of the >current< run, so there may be multiple tuples with the same
    # value.  Note that None is reserved and cannot be a value
    def generate_runs( self, values ):
        n_values = len( values )
        i_prev_value = 0
        for i_value in range( n_values ):
            # See if this is where the current run value changes:
            if values[ i_prev_value ] != values[ i_value ]:
                count = i_value - i_prev_value
                assert count > 0
                yield ( values[ i_prev_value ], count )
                i_prev_value = i_value
        count = n_values - i_prev_value
        yield ( values[ i_prev_value ], count )




'''

        n_cars = len( directions )
        directions = list( directions )
        all_collisions = 0
        while True:
            n_collisions = 0
            for i_car in range( n_cars - 1 ):
                if directions[ i_car ] == 'R' and directions[ i_car + 1 ] == 'L':
                    n_collisions += 2
                    directions[ i_car ] = directions[ i_car + 1 ] = 'S'
                elif directions[ i_car ] == 'R' and directions[ i_car + 1 ] == 'S':
                    n_collisions += 1
                    directions[ i_car ] = 'S'
                elif directions[ i_car ] == 'S' and directions[ i_car + 1 ] == 'L':
                    n_collisions += 1
                    directions[ i_car + 1 ] = 'S'
            if n_collisions:
                all_collisions += n_collisions
            else:
                break
        return all_collisions
'''

276