Elimine todos los caracteres adyacentes duplicados de una string usando Stack

Dada una string, str , la tarea es eliminar todos los caracteres adyacentes duplicados de la string dada.

Ejemplos:

Entrada: str= “axxxzy”
Salida: ay 
La eliminación de “xx” modifica la string a “azzy”. 
Ahora, la eliminación de «zz» modifica la string a «ay». 
Dado que la string «ay» no contiene duplicados, la salida es ay .

Entrada : “aaccdd”
Salida: string vacía

Enfoque recursivo: consulte el artículo Eliminación recursiva de todos los duplicados adyacentes para resolver este problema de forma recursiva. 
Complejidad temporal: O(N)
Espacio auxiliar: O(N)

Enfoque basado en funciones de string : Consulte este artículo Elimine los primeros pares adyacentes de caracteres similares hasta que sea posible resolver este problema utilizando las funciones incorporadas pop_back() y back() métodos de string .  

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

Enfoque basado en Stack : el problema se puede resolver usando Stack para usar la propiedad de LIFO . La idea es recorrer la string de izquierda a derecha y verificar si la pila está vacía o si el elemento superior de la pila no es igual al carácter actual de str , luego inserte el carácter actual en la pila. De lo contrario, saque el elemento de la parte superior de la pila . Siga los pasos a continuación para resolver el problema: 

1. Cree una pila , st para eliminar los caracteres duplicados adyacentes en str .
2. Recorra la string str y verifique si la pila está vacía o si el elemento superior de la pila no es igual al carácter actual. Si se encuentra que es cierto, inserte el carácter actual en st .
3. De lo contrario, saque el elemento de la parte superior de la pila.
4. Finalmente, imprima todos los elementos restantes de la pila.

// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to remove adjacent
// duplicate elements
string ShortenString(string str1)
{
     
    // Store the string without
    // duplicate elements
    stack<char> st;
     
    // Store the index of str
    int i = 0;
     
    // Traverse the string str
    while (i < str1.length())
    {
         
        // Checks if stack is empty or top of the
        // stack is not equal to current character
        if (st.empty() || str1[i] != st.top())
        {
            st.push(str1[i]);
            i++;
        }
             
        // If top element of the stack is
        // equal to the current character
        else
        {
            st.pop();
            i++;
        }
    }
     
    // If stack is empty
    if (st.empty())
    {
        return ("Empty String");
    }
         
    // If stack is not Empty
    else
    {
        string short_string = "";
        while (!st.empty())
        {
            short_string = st.top() +
                           short_string;
            st.pop();
        }
        return (short_string);
    }
}
 
// Driver Code
int main()
{
    string str1 ="azzxzy";
     
    cout << ShortenString(str1);
 
    return 0;
}
 
// This code is contributed by divyeshrabadiya07

// Java program to implement
// the above approach
import java.util.*;
class GFG{
 
// Function to remove adjacent
// duplicate elements
static String ShortenString(String str1)
{
  // Store the String without
  // duplicate elements
  Stack<Character> st =
        new Stack<Character>();
 
  // Store the index of str
  int i = 0;
 
  // Traverse the String str
  while (i < str1.length())
  {
    // Checks if stack is empty
    // or top of the stack is not
    // equal to current character
    if (st.isEmpty() ||
        str1.charAt(i) != st.peek())
    {
      st.add(str1.charAt(i));
      i++;
    }
 
    // If top element of the stack is
    // equal to the current character
    else
    {
      st.pop();
      i++;
    }
  }
 
  // If stack is empty
  if (st.isEmpty())
  {
    return ("Empty String");
  }
 
  // If stack is not Empty
  else
  {
    String short_String = "";
    while (!st.isEmpty())
    {
      short_String = st.peek() +
                     short_String;
      st.pop();
    }
    return (short_String);
  }
}
 
// Driver Code
public static void main(String[] args)
{
  String str1 ="azzxzy";
  System.out.print(ShortenString(str1));
 
}
}
 
// This code is contributed by Rajput-Ji

# Python3 program to implement
# the above approach
 
# Function to remove adjacent
# duplicate elements
def ShortenString(str1):
     
    # Store the string without
    # duplicate elements
    st = []
     
    # Store the index of str
    i = 0
     
    # Traverse the string str
    while i < len(str1):
         
        # Checks if stack is empty or top of the
        # stack is not equal to current character
        if len(st)== 0 or str1[i] != st[-1]:
            st.append(str1[i])
            i += 1
             
        # If top element of the stack is
        # equal to the current character
        else:
            st.pop()
            i += 1
             
    # If stack is empty
    if len(st)== 0:
        return("Empty String")
         
    # If stack is not Empty
    else:
        short_string = ""
        for i in st:
            short_string += str(i)
        return(short_string)
       
# Driver Code
if __name__ == "__main__":
    str1 ="azzxzy"
    print(ShortenString(str1))

// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to remove adjacent
// duplicate elements
static String ShortenString(String str1)
{
     
    // Store the String without
    // duplicate elements
    Stack<char> st = new Stack<char>();
     
    // Store the index of str
    int i = 0;
     
    // Traverse the String str
    while (i < str1.Length)
    {
         
        // Checks if stack is empty
        // or top of the stack is not
        // equal to current character
        if (st.Count == 0 || (st.Count != 0 &&
             str1[i] != st.Peek()))
        {
            st.Push(str1[i]);
            i++;
        }
     
        // If top element of the stack is
        // equal to the current character
        else
        {
            if (st.Count != 0)
                st.Pop();
                 
            i++;
        }
    }
     
    // If stack is empty
    if (st.Count == 0)
    {
        return ("Empty String");
    }
     
    // If stack is not Empty
    else
    {
        String short_String = "";
         
        while (st.Count != 0)
        {
            short_String = st.Peek() +
                           short_String;
            st.Pop();
        }
        return (short_String);
    }
}
 
// Driver Code
public static void Main(String[] args)
{
    String str1 ="azzxzy";
     
    Console.Write(ShortenString(str1));
}
}
 
// This code is contributed by Amit Katiyar

<script>
 
// JavaScript program to implement
// the above approach
 
// Function to remove adjacent
// duplicate elements
function ShortenString(str1)
{
     
    // Store the string without
    // duplicate elements
    var st = [];
     
    // Store the index of str
    var i = 0;
     
    // Traverse the string str
    while (i < str1.length)
    {
         
        // Checks if stack is empty or top of the
        // stack is not equal to current character
        if (st.length==0 || str1[i] != st[st.length-1])
        {
            st.push(str1[i]);
            i++;
        }
             
        // If top element of the stack is
        // equal to the current character
        else
        {
            st.pop();
            i++;
        }
    }
     
    // If stack is empty
    if (st.length==0)
    {
        return ("Empty String");
    }
         
    // If stack is not Empty
    else
    {
        var short_string = "";
        while(st.length!=0)
        {
            short_string = st[st.length-1] +
                           short_string;
            st.pop();
        }
        return (short_string);
    }
}
 
// Driver Code
var str1 ="azzxzy";
document.write( ShortenString(str1));
 
 
 
</script>

axzy

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