Eliminar todos los duplicados consecutivos de la string

Dada una string S, elimine todos los duplicados consecutivos. Tenga en cuenta que este problema es diferente de Eliminar recursivamente todos los duplicados adyacentes . Aquí mantenemos un carácter y eliminamos todos los mismos caracteres posteriores.

Ejemplos: 

Input  : aaaaabbbbbb
Output : ab

Input : geeksforgeeks
Output : geksforgeks

Input : aabccba
Output : abcba

Solución recursiva:

El problema anterior se puede resolver mediante recursividad.  

1. Si la string está vacía, regresa.
2. De lo contrario, compare los caracteres adyacentes de la string. Si son iguales, cambie los caracteres uno por uno hacia la izquierda. Llame a la recursividad en la string S
3. Si no son iguales, llame a la recursividad desde la string S+1.

El árbol de recurrencia para la string S = aabcca se muestra a continuación.  

        aabcca   S = aabcca
        /
       abcca     S = abcca        
       /
      bcca       S = abcca
      /
     cca         S = abcca
     /
    ca           S = abca
   /
  a              S = abca (Output String)
 /
empty string

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

// Recursive Program to remove consecutive
// duplicates from string S.
#include <bits/stdc++.h>
using namespace std;
 
// A recursive function that removes
// consecutive duplicates from string S
void removeDuplicates(char* S)
{
    // When string is empty, return
    if (S[0] == '\0')
        return;
 
    // if the adjacent characters are same
    if (S[0] == S[1]) {
         
        // Shift character by one to left
        int i = 0;
        while (S[i] != '\0') {
            S[i] = S[i + 1];
            i++;
        }
 
        // Check on Updated String S
        removeDuplicates(S);
    }
 
    // If the adjacent characters are not same
    // Check from S+1 string address
    removeDuplicates(S + 1);
}
 
// Driver Program
int main()
{
    char S1[] = "geeksforgeeks";
    removeDuplicates(S1);
    cout << S1 << endl;
 
    char S2[] = "aabcca";
    removeDuplicates(S2);
    cout << S2 << endl;
 
    return 0;
}

/*package whatever //do not write package name here */
 
import java.io.*;
 
class GFG {
    public static String removeConsecutiveDuplicates(String input) {
        if(input.length()<=1)
            return input;
        if(input.charAt(0)==input.charAt(1))
            return removeConsecutiveDuplicates(input.substring(1));
        else
            return input.charAt(0) + removeConsecutiveDuplicates(input.substring(1));
    }
    public static void main(String[] args)
    {
        String S1 = "geeksforgeeks";
        System.out.println(removeConsecutiveDuplicates(S1));
   
        String S2 = "aabcca";
        System.out.println(removeConsecutiveDuplicates(S2));
    }
}

# Recursive Program to remove consecutive
# duplicates from string S.
def removeConsecutiveDuplicates(s):
    if len(s)<2:
        return s
    if s[0]!=s[1]:
        return s[0]+removeConsecutiveDuplicates(s[1:])
    return removeConsecutiveDuplicates(s[1:])
 
# This code is contributed by direwolf707
s1='geeksforgeeks'
print(removeConsecutiveDuplicates(s1)) #geksforgeks
s2='aabcca'
print(removeConsecutiveDuplicates(s2)) #ab
 
# This code is contributed by rahulsood707.

/*package whatever //do not write package name here */
using System;
 
class GFG {
    public static string removeConsecutiveDuplicates(string input) {
        if(input.Length <= 1)
            return input;
        if(input[0] == input[1])
            return removeConsecutiveDuplicates(input.Substring(1));
        else
            return input[0] + removeConsecutiveDuplicates(input.Substring(1));
    }
    public static void Main(String[] args)
    {
        string S1 = "geeksforgeeks";
        Console.WriteLine(removeConsecutiveDuplicates(S1));
   
        string S2 = "aabcca";
        Console.Write(removeConsecutiveDuplicates(S2));
    }
}
 
// This code is contributed by shivanisinghss2110

<script>
 
function removeConsecutiveDuplicates(input)
{
    if(input.length<=1)
            return input;
        if(input[0]==input[1])
            return removeConsecutiveDuplicates(input.substring(1));
        else
            return input[0] +
            removeConsecutiveDuplicates(input.substring(1));
}
 
let S1 = "geeksforgeeks";
document.write(removeConsecutiveDuplicates(S1)+"<br>");
 
let  S2 = "aabcca";
document.write(removeConsecutiveDuplicates(S2)+"<br>");
 
 
// This code is contributed by rag2127
 
</script>

geksforgeks
abca

La complejidad temporal del peor de los casos de la solución anterior es O(n ² ) . El peor de los casos ocurre cuando todos los caracteres son iguales. 

Solución iterativa:

La idea es comprobar si el carácter actual es igual al carácter siguiente o no. Si el carácter actual es igual al siguiente carácter lo ignoraremos y cuando no sea igual lo agregaremos a nuestra respuesta. Dado que el último elemento no se verificará, lo empujaremos al final de la string. Por ejemplo: s=”aaaa”

cuando ejecutamos el ciclo str=”” así que al final agregaremos ‘a’ porque es el último elemento.

Implementación:

// C++ program to remove consecutive
// duplicates from a given string.
#include <bits/stdc++.h>
using namespace std;
 
// A iterative function that removes 
// consecutive duplicates from string S
string removeDuplicates(string s){
     
   int n = s.length();
   string str="";
   // We don't need to do anything for
   // empty string.
   if (n == 0)
     return str;
 
   // Traversing string
    for(int i=0;i<n-1;i++){
      //checking if s[i] is not same as s[i+1] then add it into str
        if(s[i]!=s[i+1]){
            str+=s[i];
        }
    }
  //Since the last character will not be inserted in the loop we add it at the end
   str.push_back(s[n-1]);
   return str;   
}
  
// Driver Program
int main() {
      
    string s1 = "geeksforgeeks";
    cout << removeDuplicates(s1) << endl;
     
    string s2 = "aabcca";
    cout << removeDuplicates(s2) << endl;
      
    return 0;
}

// Java program to remove consecutive
// duplicates from a given string.
import java.util.*;
 
class GFG
{
 
    // A iterative function that removes
    // consecutive duplicates from string S
    static void removeDuplicates(char[] S)
    {
        int n = S.length;
 
        // We don't need to do anything for
        // empty or single character string.
        if (n < 2)
        {
            return;
        }
 
        // j is used to store index is result
        // string (or index of current distinct
        // character)
        int j = 0;
 
        // Traversing string
        for (int i = 1; i < n; i++)
        {
            // If current character S[i]
            // is different from S[j]
            if (S[j] != S[i])
            {
                j++;
                S[j] = S[i];
            }
        }
        System.out.println(Arrays.copyOfRange(S, 0, j + 1));
    }
 
    // Driver code
    public static void main(String[] args)
    {
        char S1[] = "geeksforgeeks".toCharArray();
        removeDuplicates(S1);
 
        char S2[] = "aabcca".toCharArray();
        removeDuplicates(S2);
    }
}
 
/* This code contributed by PrinciRaj1992 */

# Python3 program to remove consecutive
# duplicates from a given string.
 
# A iterative function that removes
# consecutive duplicates from string S
def removeDuplicates(S):
         
    n = len(S)
     
    # We don't need to do anything for
    # empty or single character string.
    if (n < 2) :
        return
         
    # j is used to store index is result
    # string (or index of current distinct
    # character)
    j = 0
     
    # Traversing string
    for i in range(n):
         
        # If current character S[i]
        # is different from S[j]
        if (S[j] != S[i]):
            j += 1
            S[j] = S[i]
     
    # Putting string termination
    # character.
    j += 1
    S = S[:j]
    return S
     
# Driver Code
if __name__ == '__main__':
         
    S1 = "geeksforgeeks"
    S1 = list(S1.rstrip())
    S1 = removeDuplicates(S1)
    print(*S1, sep = "")
         
    S2 = "aabcca"
    S2 = list(S2.rstrip())
    S2 = removeDuplicates(S2)
    print(*S2, sep = "")
 
# This code is contributed by
# Shubham Singh(SHUBHAMSINGH10)

// C# program to remove consecutive
// duplicates from a given string.
using System;
     
class GFG
{
 
    // A iterative function that removes
    // consecutive duplicates from string S
    static void removeDuplicates(char[] S)
    {
        int n = S.Length;
 
        // We don't need to do anything for
        // empty or single character string.
        if (n < 2)
        {
            return;
        }
 
        // j is used to store index is result
        // string (or index of current distinct
        // character)
        int j = 0;
 
        // Traversing string
        for (int i = 1; i < n; i++)
        {
            // If current character S[i]
            // is different from S[j]
            if (S[j] != S[i])
            {
                j++;
                S[j] = S[i];
            }
        }
        char []A = new char[j+1];
        Array.Copy(S,0, A, 0, j + 1);
        Console.WriteLine(A);
    }
 
    // Driver code
    public static void Main(String[] args)
    {
        char []S1 = "geeksforgeeks".ToCharArray();
        removeDuplicates(S1);
 
        char []S2 = "aabcca".ToCharArray();
        removeDuplicates(S2);
    }
}
 
// This code is contributed by 29AjayKumar

<script>
    // JavaScript program for the above approach
 
    // duplicates from a given string.
 
    // A iterative function that removes
    // consecutive duplicates from string S
    const removeDuplicates = (s) => {
 
        let n = s.length;
        let str = "";
        // We don't need to do anything for
        // empty string.
        if (n == 0)
            return str;
 
        // Traversing string
        for (let i = 0; i < n - 1; i++) {
            //checking if s[i] is not same as s[i+1] then add it into str
            if (s[i] != s[i + 1]) {
                str += s[i];
            }
        }
        //Since the last character will not be inserted in the loop we add it at the end
         
        str += s[n-1];
        return str;
    }
 
    // Driver Program
    let s1 = "geeksforgeeks";
    document.write(`${removeDuplicates(s1)}<br/>`)
    let s2 = "aabcca";
    document.write(removeDuplicates(s2))
 
 
    // This code is contributed by rakeshsahni
 
</script>

geksforgeks
abca

Tiempo Complejidad : O(n) 
Espacio Auxiliar : O(1)

Este artículo es una contribución de Ankur Singh . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.