Eliminar los primeros pares adyacentes de caracteres similares hasta que sea posible

Dada una string Str , la tarea es eliminar los primeros pares adyacentes de caracteres similares hasta que podamos. 
Nota : elimine los caracteres adyacentes para obtener una nueva string y luego elimine nuevamente los duplicados adyacentes de la nueva string y siga repitiendo este proceso hasta que se eliminen todos los pares de caracteres adyacentes similares.
Ejemplos: 
 

Entrada: str = “keexxllx” 
Salida: kx 
Paso 0: Quite ee para obtener “kxxllx” 
Paso 1: Quite xx para obtener “kllx” 
Paso 2: Quite ll para obtener “kx” 
Entrada: str = “abbaca” 
Salida: ca 
 

Enfoque : 
use el método STL back() y pop_back() de string en C++ para resolver el problema anterior. Itere para cada carácter en la string, y si los caracteres adyacentes son iguales, elimine los caracteres adyacentes usando la función pop_back(). Al final, devuelve la string final. 
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to remove adjacent duplicates
string removeDuplicates(string S)
{
    string ans = "";
 
    // Iterate for every character
    // in the string
    for (auto it : S) {
 
        // If ans string is empty or its last
        // character does not match with the
        // current character then append this
        // character to the string
        if (ans.empty() or ans.back() != it)
            ans.push_back(it);
 
        // Matches with the previous one
        else if (ans.back() == it)
            ans.pop_back();
    }
 
    // Return the answer
    return ans;
}
 
// Driver Code
int main()
{
    string str = "keexxllx";
    cout << removeDuplicates(str);
}

// Java implementation of the above approach
class GFG
{
 
    // Function to remove adjacent duplicates
    static String removeDuplicates(String S)
    {
        String ans = "";
 
        // Iterate for every character
        // in the string
        for (int i = 0; i < S.length(); i++)
        {
 
            // If ans string is empty or its last
            // character does not match with the
            // current character then append this
            // character to the string
            if (ans.isEmpty() ||
                ans.charAt(ans.length() - 1) != S.charAt(i))
                ans += S.charAt(i);
 
            // Matches with the previous one
            else if (ans.charAt(ans.length() - 1) == S.charAt(i))
                ans = ans.substring(0, ans.length() - 1);
        }
 
        // Return the answer
        return ans;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        String str = "keexxllx";
        System.out.println(removeDuplicates(str));
    }
}
 
// This code is contributed by
// sanjeev2552

# Python3 implementation of the above approach
 
# Function to remove adjacent duplicates
def removeDuplicates(S) :
 
    ans = "";
 
    # Iterate for every character
    # in the string
    for it in S :
 
        # If ans string is empty or its last
        # character does not match with the
        # current character then append this
        # character to the string
        if (ans == "" or ans[-1] != it) :
            ans += it ;
 
        # Matches with the previous one
        elif (ans[-1] == it) :
            ans = ans[:-1];
 
    # Return the answer
    return ans;
 
 
# Driver Code
if __name__ == "__main__" :
 
    string = "keexxllx";
    print(removeDuplicates(string));
     
# This code is contributed by AnkitRai01

// C# implementation of the above approach
using System;
     
class GFG
{
 
    // Function to remove adjacent duplicates
    static String removeDuplicates(String S)
    {
        String ans = "";
 
        // Iterate for every character
        // in the string
        for (int i = 0; i < S.Length; i++)
        {
 
            // If ans string is empty or its last
            // character does not match with the
            // current character then append this
            // character to the string
            if (ans == "" ||
                ans[ans.Length - 1] != S[i])
                ans += S[i];
 
            // Matches with the previous one
            else if (ans[ans.Length - 1] == S[i])
                ans = ans.Substring(0, ans.Length - 1);
        }
 
        // Return the answer
        return ans;
    }
 
    // Driver Code
    public static void Main(String[] args)
    {
        String str = "keexxllx";
        Console.WriteLine(removeDuplicates(str));
    }
}
 
// This code is contributed by Rajput-Ji

<script>
 
// JavaScript implementation of the above approach
 
// Function to remove adjacent duplicates
     function removeDuplicates( S) {
        var ans = "";
 
        // Iterate for every character
        // in the string
        for (i = 0; i < S.length; i++) {
 
            // If ans string is empty or its last
            // character does not match with the
            // current character then append this
            // character to the string
            if (ans.length==0 ||
            ans.charAt(ans.length - 1) != S.charAt(i))
                ans += S.charAt(i);
 
            // Matches with the previous one
            else if (ans.charAt(ans.length - 1) == S.charAt(i))
                ans = ans.substring(0, ans.length - 1);
        }
 
        // Return the answer
        return ans;
    }
 
    // Driver Code
     
        var str = "keexxllx";
        document.write(removeDuplicates(str));
 
// This code contributed by Rajput-Ji
 
</script>

kx

Complejidad de tiempo: O (N), ya que estamos usando un bucle para atravesar N veces. Donde N es la longitud de la string.

Espacio auxiliar: O(N), ya que estamos usando espacio extra para la string ans. Donde N es la longitud de la string.