El recuento máximo de X que se puede insertar sin 3 caracteres adyacentes es X

Dada una string , str de longitud N y un carácter X , la tarea es encontrar la cantidad máxima de caracteres X que se insertarán en la string de modo que no haya tres caracteres consecutivos iguales a X. Si no es posible encontrar dicha string, imprima -1 .

Ejemplos:

Entrada: str = “xxyxy”, X = X 
Salida: 3 
Explicación: 
Inserte una ‘x’ en la posición 4: “xxyxxy”. 
Inserte dos ‘x’ en la posición 7: “xxyxxyxx” 
Ahora no se pueden insertar más ‘x’, ya que conducirá a una substring de tamaño 3 con todo x en ella. 
Por lo tanto, el conteo requerido es 3.

Entrada: str = «gfg», X = ‘X’ 
Salida: 8

Enfoque: la idea es contar todas las posiciones donde se puede insertar X y luego restar el recuento de X ya presentes en la string. 
A continuación se muestran los pasos:

1. El número máximo de X que se puede insertar en la string es de 2 * (N + 1) caracteres, ya que es posible insertar dos X al principio y al final de la string y entre cada carácter consecutivo.
2. Ahora, encuentra el número de grupos de X consecutivos que tienen un tamaño de 1 o 2 y guárdalo en una variable countX .
3. El número de X que se pueden insertar en la string dada es 2 * (número de lugares que se insertarán + 1) – número de X encontrados .
4. En conclusión, se puede usar una fórmula matemática simple, 2 * (N + 1) – (N – Xs) para encontrar la respuesta final.

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Utility function to find maximum count of
// X that are to be inserted into str such that
// no three consecutive characters are equal to X
int maxNumberOfXAddedUtil(string str, char X)
{
 
    // Stores count of consecutive X
    int countX = 0;
 
    // Stores count of characters which
    // is not equal to X
    int countNotX = 0;
 
    // Iterate over characters of string, str
    for (int i = 0; i < str.size(); i++)
    {
 
        // If current character is X
        if (str[i] == X)
        {
 
            // Update  countX
            countX++;
        }
 
        // If countX is less
        // than 3
        else if (countX < 3)
        {
 
            // Update countNotX
            countNotX++;
 
            // Update countX
            countX = 0;
        }
    }
 
    // If countX is greater than
    // or equal to 3
    if (countX >= 3)
        return -1;
    else
        return 2 * (countNotX + 1) - (str.size() - countNotX);
}
 
// Function to find maximum count of X that
// are to be inserted into str such that no
// three consecutive characters are equal to X
static void maxNumberOfXAdded(string str, char X)
{
 
    int ans = maxNumberOfXAddedUtil(str, X);
 
    // Print the answer
    cout << (ans);
}
 
// Driver code
int main()
{
 
    // Given string
    string str = "xxyxy";
 
    char X = 'x';
   
    // Function Call
    maxNumberOfXAdded(str, X);
}
 
// This code is contributed by amreshkumar3.

// Java program for the above approach
 
import java.util.*;
 
public class Main {
 
    // Utility function to find maximum count of
    // X that are to be inserted into str such that
    // no three consecutive characters are equal to X
    static int maxNumberOfXAddedUtil(String str, char X)
    {
 
        // Stores count of consecutive X
        int countX = 0;
 
        // Stores count of characters which
        // is not equal to X
        int countNotX = 0;
 
        // Iterate over characters of string, str
        for (int i = 0; i < str.length(); i++) {
 
            // If current character is X
            if (str.charAt(i) == X) {
 
                // Update  countX
                countX++;
            }
 
            // If countX is less
            // than 3
            else if (countX < 3) {
 
                // Update countNotX
                countNotX++;
 
                // Update countX
                countX = 0;
            }
        }
 
        // If countX is greater than
        // or equal to 3
        if (countX >= 3)
            return -1;
        else
            return 2 * (countNotX + 1)
                - (str.length() - countNotX);
    }
 
    // Function to find maximum count of X that
    // are to be inserted into str such that no
    // three consecutive characters are equal to X
    static void maxNumberOfXAdded(String str, char X)
    {
 
        int ans = maxNumberOfXAddedUtil(str, X);
 
        // Print the answer
        System.out.println(ans);
    }
 
    // Driver Code
    public static void main(String[] args)
    {
 
        // Given string
        String str = "xxyxy";
 
        char X = X;
 
        // Function Call
        maxNumberOfXAdded(str, X);
    }
}

# Python program for the above approach
 
# Utility function to find maximum count of
# X that are to be inserted into Str such that
# no three consecutive characters are equal to X
def maxNumberOfXAddedUtil(Str, X):
 
    # Stores count of consecutive X
    countX = 0
 
    # Stores count of characters which
    # is not equal to X
    countNotX = 0
 
    # Iterate over characters of String, Str
    for i in range(len(Str)):
 
        # If current character is X
        if (Str[i] == X):
 
            # Update countX
            countX += 1
 
        # If countX is less
        # than 3
        elif (countX < 3):
 
            # Update countNotX
            countNotX += 1
 
            # Update countX
            countX = 0
 
    # If countX is greater than
    # or equal to 3
    if (countX >= 3):
        return -1
    else:
        return 2 * (countNotX + 1) - (len(Str) - countNotX)
 
# Function to find maximum count of X that
# are to be inserted into Str such that no
# three consecutive characters are equal to X
def maxNumberOfXAdded(Str,X):
 
    ans = maxNumberOfXAddedUtil(Str, X)
 
    # Print the answer
    print(ans)
 
# Driver code
 
# Given String
Str = "xxyxy"
 
X = 'x'
 
# Function Call
maxNumberOfXAdded(Str, X)
 
# This code is contributed by shinjanpatra

// C# program for the above approach
using System;
 
class GFG{
 
    // Utility function to find maximum count of
    // X that are to be inserted into str such that
    // no three consecutive characters are equal to X
    static int maxNumberOfXAddedUtil(string str, char X)
    {
 
        // Stores count of consecutive X
        int countX = 0;
 
        // Stores count of characters which
        // is not equal to X
        int countNotX = 0;
 
        // Iterate over characters of string, str
        for (int i = 0; i < str.Length; i++) {
 
            // If current character is X
            if (str[i] == X) {
 
                // Update  countX
                countX++;
            }
 
            // If countX is less
            // than 3
            else if (countX < 3) {
 
                // Update countNotX
                countNotX++;
 
                // Update countX
                countX = 0;
            }
        }
 
        // If countX is greater than
        // or equal to 3
        if (countX >= 3)
            return -1;
        else
            return 2 * (countNotX + 1)
                - (str.Length - countNotX);
    }
 
    // Function to find maximum count of X that
    // are to be inserted into str such that no
    // three consecutive characters are equal to X
    static void maxNumberOfXAdded(string str, char X)
    {
 
        int ans = maxNumberOfXAddedUtil(str, X);
 
        // Print the answer
        Console.Write(ans);
    }
 
// Driver Code
public static void Main()
{
     // Given string
        string str = "xxyxy";
 
        char X = 'x';
 
        // Function Call
        maxNumberOfXAdded(str, X);
}
}
 
// This code is contributed by target_2.

<script>
 
// JavaScript program for the above approach
 
// Utility function to find maximum count of
// X that are to be inserted into str such that
// no three consecutive characters are equal to X
function maxNumberOfXAddedUtil(str, X)
{
 
    // Stores count of consecutive X
    let countX = 0;
 
    // Stores count of characters which
    // is not equal to X
    let countNotX = 0;
 
    // Iterate over characters of string, str
    for (let i = 0; i < str.length; i++)
    {
 
        // If current character is X
        if (str[i] == X)
        {
 
            // Update countX
            countX++;
        }
 
        // If countX is less
        // than 3
        else if (countX < 3)
        {
 
            // Update countNotX
            countNotX++;
 
            // Update countX
            countX = 0;
        }
    }
 
    // If countX is greater than
    // or equal to 3
    if (countX >= 3)
        return -1;
    else
        return 2 * (countNotX + 1) - (str.length - countNotX);
}
 
// Function to find maximum count of X that
// are to be inserted into str such that no
// three consecutive characters are equal to X
function maxNumberOfXAdded(str,X)
{
 
    let ans = maxNumberOfXAddedUtil(str, X);
 
    // Print the answer
    document.write(ans);
}
 
// Driver code
 
// Given string
let str = "xxyxy";
 
let X = 'x';
 
// Function Call
maxNumberOfXAdded(str, X);
 
// This code is contributed by shinjanpatra
 
</script>

3

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