Cambiar la string dada de acuerdo con las condiciones dadas

Dada una string S, la tarea es cambiar la identificación de la string que no sigue ninguna de las reglas que se indican a continuación e imprimir la string actualizada. Las reglas para la revisión son: 

1. Si hay tres caracteres consecutivos, entonces es un hechizo incorrecto. Eliminar uno de los personajes. Por ejemplo , la string «ooops» se puede cambiar a «oops» .
2. Si dos pares de los mismos caracteres (AABB) están conectados entre sí, es un hechizo incorrecto. Elimina uno de los personajes del segundo par. Por ejemplo , la string «hola» se puede cambiar a «hola» .
3. Las reglas siguen la prioridad de izquierda a derecha.

Ejemplos: 

Entrada: S = “hola”
Salida: hola
Explicación:
Según la Regla #2
hola => hola

Entrada: S = “woooow”
Salida: woow
Explicación: 
Según la Regla #2
woooow => wooow
Según la Regla #1
wooow => woow

Enfoque: la idea es atravesar la string y, si hay una ortografía incorrecta, eliminar los caracteres adicionales de acuerdo con las condiciones dadas. Como la prioridad de los errores es de izquierda a derecha, y de acuerdo con las reglas dadas, se puede ver que el juicio de errores ortográficos no entrará en conflicto. Considere atravesar de izquierda a derecha, agregando los caracteres ya legales al resultado. A continuación se muestran los pasos:

• Inicialice una pila para almacenar los caracteres y comparar los últimos caracteres de la string.
• Atraviese la string y agregue el carácter a la pila.
• Verifique los últimos 3 caracteres de la pila, si son iguales, saque el personaje en la parte superior de la pila.
• Verifique los últimos 4 caracteres de la pila, si son iguales, extraiga el carácter en la parte superior de la pila.
• Finalmente, devuelve los caracteres de la pila.

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

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to proofread the spells
string proofreadSpell(string& str)
{
    vector<char> result;
 
    // Loop to iterate over the
    // characters of the string
    for (char c : str) {
 
        // Push the current character c
        // in the stack
        result.push_back(c);
 
        int n = result.size();
 
        // Check for Rule 1
        if (n >= 3) {
            if (result[n - 1]
                    == result[n - 2]
                && result[n - 1]
                       == result[n - 3]) {
                result.pop_back();
            }
        }
        n = result.size();
 
        // Check for Rule 2
        if (n >= 4) {
            if (result[n - 1]
                    == result[n - 2]
                && result[n - 3]
                       == result[n - 4]) {
                result.pop_back();
            }
        }
    }
 
    // To store the resultant string
    string resultStr = "";
 
    // Loop to iterate over the
    // characters of stack
    for (char c : result) {
        resultStr += c;
    }
 
    // Return the resultant string
    return resultStr;
}
 
// Driver Code
int main()
{
    // Given string str
    string str = "hello";
 
    // Function Call
    cout << proofreadSpell(str);
}

// Java program for the above approach
import java.util.*;
 
class GFG{
     
// Function to proofread the spells
public static String proofreadSpell(String str)
{
    Vector<Character> result = new Vector<Character>();
 
    // Loop to iterate over the
    // characters of the string
    for(int i = 0; i < str.length(); i++)
    {
         
        // Push the current character c
        // in the stack
        result.add(str.charAt(i));
 
        int n = result.size();
 
        // Check for Rule 1
        if (n >= 3)
        {
            if (result.get(n - 1) ==
                result.get(n - 2) &&
                result.get(n - 1) ==
                result.get(n - 3))
            {
                result.remove(result.size() - 1);
            }
        }
        n = result.size();
 
        // Check for Rule 2
        if (n >= 4)
        {
            if (result.get(n - 1) ==
                result.get(n - 2) &&
                result.get(n - 3) ==
                result.get(n - 4))
            {
                result.remove(result.size() - 1);
            }
        }
    }
 
    // To store the resultant string
    String resultStr = "";
 
    // Loop to iterate over the
    // characters of stack
    for(Character c : result)
    {
        resultStr += c;
    }
     
    // Return the resultant string
    return resultStr;
}
 
// Driver Code
public static void main(String[] args)
{
     
    // Given string str
    String str = "hello";
 
    // Function call
    System.out.println(proofreadSpell(str));
}
}
 
// This code is contributed by divyeshrabadiya07

# Python3 program for
# the above approach
 
# Function to proofread
# the spells
def proofreadSpell(str):
   
    result = []
 
    # Loop to iterate over the
    # characters of the string
    for c in str:
 
        # Push the current character c
        # in the stack
        result.append(c)
        n = len(result)
 
        # Check for Rule 1
        if(n >= 3):
            if(result[n - 1] == result[n - 2] and
               result[n - 1] == result[n - 3]):
                result.pop()
        n = len(result)
 
        # Check for Rule 2
        if(n >= 4):
            if(result[n - 1] == result[n - 2] and
               result[n - 3] == result[n - 4]):
                result.pop()
 
    # To store the
    # resultant string
    resultStr = ""
 
    # Loop to iterate over the
    # characters of stack
    for c in result:
        resultStr += c
 
    # Return the resultant string
    return resultStr
 
# Driver Code
 
# Given string str
str = "hello"
 
# Function Call
print(proofreadSpell(str))
 
# This code is contributed by avanitrachhadiya2155

// C# program for the above approach 
using System;
using System.Collections;
using System.Collections.Generic;
 
class GFG{
 
// Function to proofread the spells
static string proofreadSpell(string str)
{
     
    // ArrayList result=new ArrayList();
    List<char> result = new List<char>();
     
    // Loop to iterate over the
    // characters of the string
    foreach(char c in str)
    {
 
        // Push the current character c
        // in the stack
        result.Add(c);
 
        int n = result.Count;
 
        // Check for Rule 1
        if (n >= 3)
        {
            if (result[n - 1] == result[n - 2] &&
                result[n - 1] == result[n - 3])
            {
                result.RemoveAt(n - 1);
            }
        }
         
        n = result.Count;
 
        // Check for Rule 2
        if (n >= 4)
        {
            if (result[n - 1] == result[n - 2] &&
                result[n - 3] == result[n - 4])
            {
                result.RemoveAt(n - 1);
            }
        }
    }
 
    // To store the resultant string
    string resultStr = "";
 
    // Loop to iterate over the
    // characters of stack
    foreach(char c in result)
    {
        resultStr += c;
    }
 
    // Return the resultant string
    return resultStr;
}
 
// Driver code
public static void Main(string[] args)
{
     
    // Given string str
    string str = "hello";
 
    // Function call
    Console.Write(proofreadSpell(str));
}
}
 
// This code is contributed by rutvik_56

<script>
 
// Javascript program for the above approach
 
// Function to proofread the spells
function proofreadSpell(str)
{
    var result = [];
 
    // Loop to iterate over the
    // characters of the string
    str.split('').forEach(c => {
        
        // Push the current character c
        // in the stack
        result.push(c);
 
        var n = result.length;
 
        // Check for Rule 1
        if (n >= 3) {
            if (result[n - 1]
                    == result[n - 2]
                && result[n - 1]
                       == result[n - 3]) {
                result.pop();
            }
        }
        n = result.length;
 
        // Check for Rule 2
        if (n >= 4) {
            if (result[n - 1]
                    == result[n - 2]
                && result[n - 3]
                       == result[n - 4]) {
                result.pop();
            }
        }
    });
 
    // To store the resultant string
    var resultStr = "";
 
    // Loop to iterate over the
    // characters of stack
    result.forEach(c => {
         
        resultStr += c;
    });
 
    // Return the resultant string
    return resultStr;
}
 
// Driver Code
// Given string str
var str = "hello";
// Function Call
document.write( proofreadSpell(str));
 
 
</script>

hello

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