Número mínimo de inserciones en una string dada para eliminar duplicados adyacentes

Dada una string str de tamaño N , la tarea es encontrar el número mínimo de adiciones en la string de modo que no haya dos elementos consecutivos iguales.

Ejemplos:

Entrada: str=”rrg” 
Salida: 1
Explicación: Agregar un elemento entre dos r

Entrada: str=”rrrrr”
Salida: 4

Enfoque: el problema anterior se puede resolver siguiendo los pasos que se indican a continuación:

1. Declare la variable min_steps e inicialícela en 0.
2. Atraviese la string usando un ciclo for de i=0 a i<N .
3. Compruebe si el carácter actual es el mismo que el carácter anterior.
4. En caso afirmativo, incremente min_steps en 1.
5. De lo contrario, continúa el bucle.
6. Imprime min_steps como respuesta .

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
 
#include <iostream>
using namespace std;
 
// Function to find the minimum
// number of additions such that
// no two elements are the same
int minAdditions(string str)
{
    // Storing length of the string
    int len = str.size();
 
    // Variable to store
    // the number of steps needed
    int min_steps = 0;
 
    int i;
 
    // For loop to check
    // all colours in the string
    for (i = 1; i < len; i++) {
        if (str[i] == str[i - 1])
            min_steps++;
    }
 
    // Returning the number of additions
    return min_steps;
}
 
// Driver Code
int main()
{
    string str = "RRG";
    cout << minAdditions(str);
    return 0;
}

// Java program for above approach
import java.util.*;
public class GFG {
 
  // Function to find the minimum
  // number of additions such that
  // no two elements are the same
  static int minAdditions(String str)
  {
 
    // Storing length of the string
    int len = str.length();
 
    // Variable to store
    // the number of steps needed
    int min_steps = 0;
 
    int i;
 
    // For loop to check
    // all colours in the string
    for (i = 1; i < len; i++) {
      if (str.charAt(i) == str.charAt(i - 1))
        min_steps++;
    }
 
    // Returning the number of additions
    return min_steps;
  }
 
  // Driver Code
  public static void main(String args[])
  {
    String str = "RRG";
 
    System.out.println(minAdditions(str));
  }
}
 
// This code is contributed by Samim Hossain Mondal.

# python3 program for the above approach
 
# Function to find the minimum
# number of additions such that
# no two elements are the same
def minAdditions(str):
 
    # Storing length of the string
    le = len(str)
 
    # Variable to store
    # the number of steps needed
    min_steps = 0
 
    # For loop to check
    # all colours in the string
    for i in range(1, le):
        if (str[i] == str[i - 1]):
            min_steps += 1
 
    # Returning the number of additions
    return min_steps
 
 
# Driver Code
if __name__ == "__main__":
 
    str = "RRG"
    print(minAdditions(str))
 
# This code is contributed by rakeshsahni

// C# program for the above approach
using System;
class GFG {
 
  // Function to find the minimum
  // number of additions such that
  // no two elements are the same
  static int minAdditions(string str)
  {
 
    // Storing length of the string
    int len = str.Length;
 
    // Variable to store
    // the number of steps needed
    int min_steps = 0;
 
    int i;
 
    // For loop to check
    // all colours in the string
    for (i = 1; i < len; i++) {
      if (str[i] == str[i - 1])
        min_steps++;
    }
 
    // Returning the number of additions
    return min_steps;
  }
 
  // Driver Code
  public static void Main()
  {
    string str = "RRG";
    Console.Write(minAdditions(str));
  }
}
 
// This code is contributed by ukasp.

<script>
// Javascript program for the above approach
 
// Function to find the minimum
// number of additions such that
// no two elements are the same
function minAdditions(str)
{
 
    // Storing length of the string
    let len = str.length;
 
    // Variable to store
    // the number of steps needed
    let min_steps = 0;
 
    let i;
 
    // For loop to check
    // all colours in the string
    for (i = 1; i < len; i++) {
        if (str[i] == str[i - 1])
            min_steps++;
    }
 
    // Returning the number of additions
    return min_steps;
}
 
// Driver Code
 
let str = "RRG";
document.write(minAdditions(str))
 
// This code is contributed by gfgking.
</script>

1

Complejidad temporal: O(N)
Espacio auxiliar: O(1)