Encuentre el número total de colisiones que tienen lugar entre las bolas en las que se da la dirección inicial de cada bola

Dado N bolas en una línea. La dirección inicial de cada bola está representada por la cuerda que consta de solo ‘L’ y ‘R’ para la dirección izquierda y derecha respectivamente. Se da que ambas bolas invierten su dirección después de la colisión y la velocidad permanecerá igual antes y después de la colisión. Calcular el número total de la colisión que tiene lugar.
Ejemplos:
 

Input: str = "RRLL"
Output: 4

Explanation
After first collision: RLRL
After second collision: LRRL
After third collision: LRLR
After fourth collision: LLRR

Input: str = "RRLR"
Output:  2

Explanation
After first collision: RLRR
After second collision: LRRR

Enfoque:
en cada etapa tenemos que encontrar el número de substrings «RL», cambiar la substring «RL» a «LR», y nuevamente contar el número de substrings «RL» en la string resultante y repetir lo siguiente hasta que no haya más la substring «RL» está disponible. No vamos a contar el número de la substring «RL» en cada etapa, ya que consumirá mucho tiempo. Otra forma de hacerlo es observar que las siguientes strings resultantes que hemos visto en cada etapa –> “RRLL” -> “RLRL”-> “LRLR” ->”LLRR”. 
La string inicial es «RRLL». tengamos una tercera bola cuya dirección sea L. Ahora observe que esta L se desplaza hacia el lado izquierdo de la cuerda. A medida que intercambiamos «RL» por «LR», desplazamos esa L hacia el lado izquierdo de la string completa. Ahora, de manera similar, si continuamos este intercambio, esta L se enfrentará a cada R que está presente en el lado izquierdo de esa string, formando nuevamente «RL». Por lo tanto, para este L, el número total de «RL» será el número total de R que está presente en el lado izquierdo de ese L particular. Repetiremos esto para cada L. Por lo tanto, en general, para contar todos los posibles substring «RL» en cada etapa, contaremos el número total de representación del lado izquierdo de cada L, ya que estos R y L formarán «RL» en cada etapa, lo que se puede hacer en complejidad de tiempo lineal.
A continuación se muestra la implementación del enfoque anterior:
 

// C++ implementation to Find total
// no of collisions taking place between
// the balls in which initial direction
// of each ball is given
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to count no of collision
int count(string s)
{
    int N, i, cnt = 0, ans = 0;
 
    // length of the string
    N = s.length();
 
    for (i = 0; i < N; i++) {
        if (s[i] == 'R')
            cnt++;
 
        if (s[i] == 'L')
            ans += cnt;
    }
 
    return ans;
}
 
// Driver code
int main()
{
 
    string s = "RRLL";
 
    cout << count(s) << endl;
 
    return 0;
}

// Java implementation to Find total
// no of collisions taking place between
// the balls in which initial direction
// of each ball is given
import java.io.*;
class GFG {
      
// Function to count
// no of collision
static int count(String s)
{
  int N, i, cnt = 0, ans = 0;
 
  // length of the string
  N = s.length();
 
  for (i = 0; i < N; i++)
  {
    if (s.charAt(i) == 'R')
      cnt++;
 
    if (s.charAt(i) == 'L')
      ans += cnt;
  }
  return ans;
}
  
// Driver code
static public void main(String[] args)
{
  String s = "RRLL";
  System.out.println(count(s));
}
}
 
// This code is contributed by Rutvik_56

# Python3 implementation to find total
# no of collisions taking place between
# the balls in which initial direction
# of each ball is given
 
# Function to count no of collision
def count(s):
 
    cnt, ans = 0, 0
 
    # Length of the string
    N = len(s)
 
    for i in range(N):
        if (s[i] == 'R'):
            cnt += 1
 
        if (s[i] == 'L'):
            ans += cnt
     
    return ans
 
# Driver code
s = "RRLL"
 
print( count(s))
 
# This code is contributed by chitranayal

// C# implementation to Find total
// no of collisions taking place between
// the balls in which initial direction
// of each ball is given
using System;
 
class GFG{
 
// Function to count no of collision
static int count(String s)
{
    int N, i, cnt = 0, ans = 0;
 
    // length of the string
    N = s.Length;
 
    for(i = 0; i < N; i++)
    {
        if (s[i] == 'R')
            cnt++;
 
        if (s[i] == 'L')
            ans += cnt;
    }
    return ans;
}
 
// Driver code
public static void Main(String[] args)
{
    String s = "RRLL";
 
    Console.Write(count(s));
}
}
 
// This code is contributed by shivanisinghss2110

<script>
  // Javascript implementation to Find total
  // no of collisions taking place between
  // the balls in which initial direction
  // of each ball is given
   
  // Function to count no of collision
  function count(s)
  {
      let N, i, cnt = 0, ans = 0;
 
      // length of the string
      N = s.length;
 
      for (i = 0; i < N; i++) {
          if (s[i] == 'R')
              cnt++;
 
          if (s[i] == 'L')
              ans += cnt;
      }
 
      return ans;
  }
   
  let s = "RRLL";
  
  document.write(count(s));
 
// This code is contributed by divyesh072019.
</script>

4

Complejidad de tiempo: O(N)

Espacio Auxiliar: O(1)