Reemplazos mínimos en una string para hacer que los caracteres adyacentes sean desiguales

Dada una string de caracteres en minúscula str de tamaño N . En una operación, cualquier carácter se puede cambiar a algún otro carácter. La tarea es encontrar el número mínimo de operaciones tal que no haya dos caracteres adyacentes iguales.
Ejemplos:

Entrada: Str = “caaab” 
Salida: 1 
Explicación: 
Cambie la segunda a por cualquier otro carácter, cambiémosla por b . Entonces la string se convierte en «cabab». y no hay dos caracteres adyacentes iguales. Por lo tanto, el número mínimo de operaciones es 1.
Entrada: Str = “xxxxxxx” 
Salida: 3 
Explicación: 
Reemplace ‘x’ en el índice 1, 3 y 5 por ‘a’, ‘b’ y ‘c’ respectivamente.

Planteamiento:  La idea es similar a implementar la técnica de la ventana corrediza . En esto, necesitamos encontrar las substrings que no se superponen y que tienen todos los caracteres iguales. Entonces las operaciones mínimas serán la suma del piso de la mitad de la longitud de cada substring.

1. No hay necesidad de cambiar un personaje directamente. En su lugar, considere todas las substrings iniciadas desde cualquier índice que tenga un solo carácter.
2. Ahora considere cualquier substring de longitud l tal que todos los caracteres de esa substring sean iguales y luego cambie los caracteres del piso (l / 2) de esta substring a algún otro carácter.
3. Entonces, simplemente itere sobre todos los caracteres de la string desde cualquier carácter ch para averiguar la longitud máxima de la substring de modo que todos los caracteres en esa substring sean iguales al carácter ch .
4. Encuentre la longitud l de esta substring y agregue piso ( l / 2) a ans .
5. Después de eso, comience desde el carácter justo al lado del final de la substring anterior.

// C++ program to find minimum
// replacements in a string to
// make adjacent characters unequal
 
#include <bits/stdc++.h>
using namespace std;
 
// Function which counts the minimum
// number of required operations
void count_minimum(string s)
{
    // n stores the length of the string s
    int n = s.length();
 
    // ans will store the required ans
    int ans = 0;
 
    // i is the current index in the string
    int i = 0;
 
    while (i < n) {
 
        int j = i;
 
        // Move j until characters s[i] & s[j]
        // are equal or the end of the
        // string is reached
        while (s[j] == s[i] && j < n) {
            j++;
        }
 
        // diff stores the length of the
        // substring such that all the
        // characters are equal in it
        int diff = j - i;
 
        // We need atleast diff/2 operations
        // for this substring
        ans += diff / 2;
        i = j;
    }
 
    cout << ans << endl;
}
 
// Driver code
int main()
{
    string str = "caaab";
    count_minimum(str);
    return 0;
}

// Java program to find minimum
// replacements in a string to
// make adjacent characters unequal
import java.util.*;
 
class GFG{
 
// Function which counts the minimum
// number of required operations
static void count_minimum(String s)
{
     
    // n stores the length of the string s
    int n = s.length();
 
    // ans will store the required ans
    int ans = 0;
 
    // i is the current index in the string
    int i = 0;
 
    while (i < n)
    {
        int j = i;
 
        // Move j until characters s[i] & s[j]
        // are equal or the end of the
        // string is reached
        while (j < n && s.charAt(j) ==
                        s.charAt(i))
        {
            j++;
        }
 
        // diff stores the length of the
        // substring such that all the
        // characters are equal in it
        int diff = j - i;
 
        // We need atleast diff/2 operations
        // for this substring
        ans += diff / 2;
        i = j;
    }
    System.out.println(ans);
}
 
// Driver code
public static void main(String[] args)
{
    String str = "caaab";
 
    count_minimum(str);
}
}
 
// This code is contributed by offbeat

# Python3 program to find minimum
# replacements in a string to
# make adjacent characters unequal
 
# Function which counts the minimum
# number of required operations
def count_minimum(s):
     
    # n stores the length of the string s
    n = len(s)
 
    # ans will store the required ans
    ans = 0
     
    # i is the current index in the string
    i = 0
     
    while i < n:
        j = i
         
        # Move j until characters s[i] & s[j]
        # are equal or the end of the
        # string is reached
        while j < n and (s[j] == s[i]):
            j += 1
         
        # diff stores the length of the
        # substring such that all the
        # characters are equal in it
        diff = j - i
         
        # We need atleast diff/2 operations
        # for this substring
        ans += diff // 2
        i = j
         
    print(ans)
     
# Driver code
if __name__=="__main__":
     
    str = "caaab"
    count_minimum(str)
     
# This code is contributed by rutvik_56

// C# program to find minimum
// replacements in a string to
// make adjacent characters unequal
using System;
 
class GFG{
     
// Function which counts the minimum
// number of required operations
static void count_minimum(string s)
{
     
    // n stores the length of the string s
    int n = s.Length;
 
    // ans will store the required ans
    int ans = 0;
 
    // i is the current index in the string
    int i = 0;
 
    while (i < n)
    {
        int j = i;
 
        // Move j until characters s[i] & s[j]
        // are equal or the end of the
        // string is reached
        while (j < n && s[j] == s[i])
        {
            j++;
        }
 
        // diff stores the length of the
        // substring such that all the
        // characters are equal in it
        int diff = j - i;
 
        // We need atleast diff/2 operations
        // for this substring
        ans += diff / 2;
        i = j;
    }
    Console.WriteLine(ans);
}
 
// Driver code
static void Main()
{
    string str = "caaab";
     
    count_minimum(str);
}
}
 
// This code is contributed by divyeshrabadiya07

<script>
      // JavaScript program to find minimum
      // replacements in a string to
      // make adjacent characters unequal
 
      // Function which counts the minimum
      // number of required operations
      function count_minimum(s) {
        // n stores the length of the string s
        var n = s.length;
 
        // ans will store the required ans
        var ans = 0;
 
        // i is the current index in the string
        var i = 0;
 
        while (i < n) {
          var j = i;
 
          // Move j until characters s[i] & s[j]
          // are equal or the end of the
          // string is reached
          while (s[j] === s[i] && j < n) {
            j++;
          }
 
          // diff stores the length of the
          // substring such that all the
          // characters are equal in it
          var diff = j - i;
 
          // We need atleast diff/2 operations
          // for this substring
          ans += parseInt(diff / 2);
          i = j;
        }
 
        document.write(ans + "<br>");
      }
 
      // Driver code
      var str = "caaab";
      count_minimum(str);
    </script>

1

Tiempo Complejidad: O (N)

Espacio Auxiliar: O (1)