Eliminación de duplicados de una cadena en Java

Question

Estoy intentando iterar a través de una cadena para eliminar los caracteres duplicados.

Por ejemplo, la cadena aabbccdef debe convertirse en abcdef y la cadena abcdabcd debe convertirse en abcd

Esto es lo que tengo hasta ahora:

public class test { 

    public static void main(String[] args) { 

     String input = new String("abbc"); 
     String output = new String(); 

     for (int i = 0; i < input.length(); i++) { 
      for (int j = 0; j < output.length(); j++) { 
       if (input.charAt(i) != output.charAt(j)) { 
        output = output + input.charAt(i); 
       } 
      } 
     } 

     System.out.println(output); 

    } 

} 

¿Cuál es la mejor manera de hacer esto?

Answer 1

convertir la cadena en una matriz de char, y almacenarlo en un LinkedHashSet. Eso preservará su orden y eliminará duplicados. Algo así como:

String string = "aabbccdefatafaz"; 

char[] chars = string.toCharArray(); 
Set<Character> charSet = new LinkedHashSet<Character>(); 
for (char c : chars) { 
    charSet.add(c); 
} 

StringBuilder sb = new StringBuilder(); 
for (Character character : charSet) { 
    sb.append(character); 
} 
System.out.println(sb.toString()); 

Answer 2

Crea un StringWriter. Ejecute la cadena original usando charAt (i) en un ciclo for. Mantenga una variable de tipo char manteniendo el último valor de charAt. Si itera y el valor de charAt es igual a lo que está almacenado en esa variable, no lo agregue al StringWriter. Finalmente, use el método StringWriter.toString() y obtenga una cadena, y haga lo que necesite con ella.

Answer 3

No puede. Puede crear una nueva Cadena que tenga duplicados eliminados. ¿Por qué no estás usando StringBuilder (o StringBuffer, presumiblemente)?

Puede ejecutar la cadena y almacenar los caracteres únicos en una matriz char [], haciendo un seguimiento de la cantidad de caracteres únicos que ha visto. Luego puede crear una nueva Cadena usando el constructor String(char[], int, int).

Además, el problema es un poco ambiguo — hace “ duplicados ” significa repeticiones adyacentes? (En otras palabras, ¿qué debería pasar con abcab?)

Answer 4

Utilizaría la ayuda de LinkedHashSet. Elimina dups (ya que estamos utilizando un conjunto, mantiene el orden ya que estamos utilizando la lista vinculada impl). Esta es una especie de solución sucia. podría haber incluso una mejor manera.

String s="aabbccdef"; 
Set<Character> set=new LinkedHashSet<Character>(); 
for(char c:s.toCharArray()) 
{ 
    set.add(Character.valueOf(c)); 
} 

Answer 5

public class RemoveRepeated4rmString { 

    public static void main(String[] args) { 
     String s = "harikrishna"; 
     String s2 = ""; 
     for (int i = 0; i < s.length(); i++) { 
      Boolean found = false; 
      for (int j = 0; j < s2.length(); j++) { 
       if (s.charAt(i) == s2.charAt(j)) { 
        found = true; 
        break; //don't need to iterate further 
       } 
      } 
      if (found == false) { 
       s2 = s2.concat(String.valueOf(s.charAt(i))); 
      } 
     } 
     System.out.println(s2); 
    } 
} 

Answer 6

String input = "AAAB"; 

    String output = ""; 
    for (int index = 0; index < input.length(); index++) { 
     if (input.charAt(index % input.length()) != input 
       .charAt((index + 1) % input.length())) { 

      output += input.charAt(index); 

     } 
    } 
    System.out.println(output); 

pero no puedes usarlo si la entrada tiene los mismos elementos, o si su vacío!

Answer 7

Bueno chicos, he encontrado una mejor manera de hacer esto

public static void alpha(char[] finalname) 
{ 
    if (finalname == null) 
    { 
     return; 
    } 

    if (finalname.length <2) 
    { 
     return; 
    } 

    char empty = '\000'; 
    for (int i=0; i<finalname.length-1; i++) 
    { 
     if (finalname[i] == finalname[i+1]) 
     { 
      finalname[i] = empty; 
     } 
    } 

    String alphaname = String.valueOf(finalname); 
    alphaname = alphaname.replace("\000", ""); 
    System.out.println(alphaname); 


} 

Answer 8

Pruebe esta solución sencilla:

public String removeDuplicates(String input){ 
    String result = ""; 
    for (int i = 0; i < input.length(); i++) { 
     if(!result.contains(String.valueOf(input.charAt(i)))) { 
      result += String.valueOf(input.charAt(i)); 
     } 
    } 
    return result; 
} 

Answer 9

manera Oldschool (como escribimos unas tareas tales in Apple] [Básico, adaptado a Java):

int i,j; 
StringBuffer str=new StringBuffer(); 
Scanner in = new Scanner(System.in); 
System.out.print("Enter string: "); 
str.append(in.nextLine()); 

for (i=0;i<str.length()-1;i++){ 
    for (j=i+1;j<str.length();j++){ 
     if (str.charAt(i)==str.charAt(j)) 
      str.deleteCharAt(j); 
    } 
} 
System.out.println("Removed non-unique symbols: " + str); 

Answer 10

Código para eliminar los caracteres duplicados en una cadena sin utilizar ningún búfer adicional. NOTA: Una o dos variables adicionales están bien.Una matriz extra no es:

import java.util.*; 
public class Main{ 
    public static char[] removeDupes(char[] arr){ 
     if (arr == null || arr.length < 2) 
      return arr; 
     int len = arr.length; 
     int tail = 1; 
     for(int x = 1; x < len; x++){ 
      int y; 
      for(y = 0; y < tail; y++){ 
       if (arr[x] == arr[y]) break; 
      } 
      if (y == tail){ 
       arr[tail] = arr[x]; 
       tail++; 
      } 
     } 
     return Arrays.copyOfRange(arr, 0, tail); 
    } 

    public static char[] bigArr(int len){ 
     char[] arr = new char[len]; 
     Random r = new Random(); 
     String alphabet = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890!@#$%^&*()-=_+[]{}|;:',.<>/?`~"; 

     for(int x = 0; x < len; x++){ 
      arr[x] = alphabet.charAt(r.nextInt(alphabet.length())); 
     } 

     return arr; 
    } 
    public static void main(String args[]){ 

     String result = new String(removeDupes(new char[]{'a', 'b', 'c', 'd', 'a'})); 
     assert "abcd".equals(result) : "abcda should return abcd but it returns: " + result; 

     result = new String(removeDupes(new char[]{'a', 'a', 'a', 'a'})); 
     assert "a".equals(result) : "aaaa should return a but it returns: " + result; 

     result = new String(removeDupes(new char[]{'a', 'b', 'c', 'a'})); 
     assert "abc".equals(result) : "abca should return abc but it returns: " + result; 

     result = new String(removeDupes(new char[]{'a', 'a', 'b', 'b'})); 
     assert "ab".equals(result) : "aabb should return ab but it returns: " + result; 

     result = new String(removeDupes(new char[]{'a'})); 
     assert "a".equals(result) : "a should return a but it returns: " + result; 

     result = new String(removeDupes(new char[]{'a', 'b', 'b', 'a'})); 
     assert "ab".equals(result) : "abba should return ab but it returns: " + result; 


     char[] arr = bigArr(5000000); 
     long startTime = System.nanoTime(); 
     System.out.println("2: " + new String(removeDupes(arr))); 
     long endTime = System.nanoTime(); 
     long duration = (endTime - startTime); 
     System.out.println("Program took: " + duration + " nanoseconds"); 
     System.out.println("Program took: " + duration/1000000000 + " seconds"); 

    } 
} 

Cómo leer y hablar sobre el código anterior:

1. El método llamado removeDupes toma una matriz de char primitivo llamado arr.
2. arr se devuelve como una matriz de caracteres primitivos "por valor". El archivo pasado es basura recolectada al final del método miembro de Main, removeDupes.
3. La complejidad del tiempo de ejecución de este algoritmo es O (n) o más específicamente O (n + (pequeña constante)) siendo la constante los caracteres únicos en toda la matriz de caracteres primitivos.
4. El copyOfRange no aumenta significativamente la complejidad del tiempo de ejecución ya que solo copia una pequeña cantidad constante de elementos. La matriz de caracteres llamada arr no tiene un paso completo.
5. Si pasa null a removeDupes, el método devuelve null.
6. Si pasa una matriz vacía de caracteres primitivos o una matriz que contiene un valor, se devuelve esa matriz no modificada.
7. El método removeDupes se ejecuta lo más rápido posible físicamente, utilizando completamente el caché L1 y L2, por lo que Branch redirects are kept to a minimum.
8. Una computadora no cargada de emisión estándar de 2015 debería ser capaz de completar este método con una matriz de caracteres primitiva que contenga 500 millones de caracteres entre 15 y 25 segundos.

explicar cómo funciona este código:

La primera parte de la matriz pasada en se utiliza como repositorio para los caracteres únicos que se devuelven en última instancia. Al comienzo de la función, la respuesta es: "los caracteres entre 0 y 1" están entre 0 y la cola.

Definimos la variable y fuera del bucle porque queremos encontrar el primer lugar en el índice de matriz que estamos viendo se ha duplicado en nuestro repositorio. Cuando se encuentra un duplicado, se rompe y se cierra, y == tail devuelve false y no se contribuye al repositorio.

cuando el índice x que estamos mirando no está representado en nuestro repositorio, luego lo jalamos y lo agregamos al final de nuestro repositorio en la cola de índice e incrementamos la cola.

Al final, volvemos la matriz entre los puntos 0 y cola, que debe ser menor o igual a la longitud de la matriz original.

Los puntos de conversación ejercicio para entrevistas codificador:

¿El programa comportarse de manera diferente si se cambia la ordenada ++ a ++ y? Por qué o por qué no.

¿La copia matriz al final representan otro pase 'N' a través de toda la matriz haciendo tiempo de ejecución complejidad O (n * n) en lugar de O (n)? Por qué o por qué no.

¿Se puede reemplazar el doble igual por la comparación de caracteres primitivos con un .equals? ¿Por qué o por qué no?

¿Puede este método puede cambiar con el fin de hacer los reemplazos "por referencia" en lugar de como es ahora, "por valor"? ¿Por qué o por qué no?

¿Se puede aumentar la eficacia de este algoritmo clasificando el repositorio de valores únicos al principio de 'arr'? ¿En qué circunstancias sería más eficiente?

Answer 11

Aquí hay otra lógica que me gustaría compartir. Empiezas a comparar desde la mitad de la longitud de la cuerda e ir hacia atrás.

Prueba con: input = "azxxzy"; output = "ay";

String removeMidway(String input){ 
     cnt = cnt+1; 
     StringBuilder str = new StringBuilder(input); 
     int midlen = str.length()/2; 
     for(int i=midlen-1;i>0;i--){ 

      for(int j=midlen;j<str.length()-1;j++){  
       if(str.charAt(i)==str.charAt(j)){ 
        str.delete(i, j+1); 
        midlen = str.length()/2; 
        System.out.println("i="+i+",j="+j+ ",len="+ str.length() + ",midlen=" + midlen+ ", after deleted = " + str); 
       } 
      } 
     }  
     return str.toString(); 
    } 

Answer 12

Aquí hay una mejora en el answer by Dave.

Se utiliza en lugar de la HashSetLinkedHashSet un poco más costoso, y reutiliza el búfer chars para el resultado, lo que elimina la necesidad de un StringBuilder.

String string = "aabbccdefatafaz"; 

char[] chars = string.toCharArray(); 
Set<Character> present = new HashSet<>(); 
int len = 0; 
for (char c : chars) 
    if (present.add(c)) 
     chars[len++] = c; 

System.out.println(new String(chars, 0, len)); // abcdeftz 

Answer 13

Este es otro enfoque

void remove_duplicate (char* str, int len) { 
    unsigned int index = 0; 
    int c = 0; 
    int i = 0; 
    while (c < len) { 
     /* this is just example more check can be added for 
      capital letter, space and special chars */ 

     int pos = str[c] - 'a'; 
     if ((index & (1<<pos)) == 0) { 
      str[i++] = str[c]; 
      index |= (1<<pos); 
     } 
     c++; 
    } 
    str[i] = 0; 
} 

Answer 14

Otra solución posible, en caso de que una cadena es una cadena ASCII, es la de mantener una serie de 256 elementos booleanos para denotar aparición de caracteres ASCII en una cadena. Si un personaje apareció por primera vez, lo guardamos y añadimos al resultado. De lo contrario, sáltelo.

Este enfoque también funcionará con la cadena Unicode. Solo necesita aumentar el tamaño de chars.

Answer 15

solución utilizando JDK7:

public static String removeDuplicateChars(final String str){ 

    if (str == null || str.isEmpty()){ 
     return str; 
    } 

    final char[] chArray = str.toCharArray(); 
    final Set<Character> set = new LinkedHashSet<>(); 
    for (char c : chArray) { 
     set.add(c); 
    } 

    final StringBuilder sb = new StringBuilder(); 
    for (Character character : set) { 
     sb.append(character); 
    } 
    return sb.toString(); 
} 

Answer 16

public static void main(String a[]){ 
     String name="Madan"; 
     System.out.println(name); 
     StringBuilder sb=new StringBuilder(name); 
     for(int i=0;i<name.length();i++){ 
      for(int j=i+1;j<name.length();j++){ 
      if(name.charAt(i)==name.charAt(j)){ 
       sb.deleteCharAt(j); 

      } 
      } 
     } 
    System.out.println("After deletion :"+sb+""); 

    } 

Answer 17

String str = "eamparuthik@gmail.com"; 
    char[] c = str.toCharArray(); 
    String op = ""; 

    for(int i=0; i<=c.length-1; i++){ 
     if(!op.contains(c[i] + "")) 
     op = op + c[i]; 
    } 
    System.out.println(op); 

Answer 18

public static String removeDuplicateChar(String str){ 
     char charArray[] = str.toCharArray(); 
     StringBuilder stringBuilder= new StringBuilder(); 
     for(int i=0;i<charArray.length;i++){ 
      int index = stringBuilder.toString().indexOf(charArray[i]); 
      if(index <= -1){ 
       stringBuilder.append(charArray[i]); 
      } 
     } 
     return stringBuilder.toString(); 
    } 

Answer 19

import java.io.BufferedReader; 
import java.io.IOException; 
import java.io.InputStreamReader; 

public class RemoveDuplicacy 
{ 
     public static void main(String args[])throws IOException 
     { 
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
      System.out.print("Enter any word : "); 
      String s = br.readLine(); 
      int l = s.length(); 
      char ch; 
      String ans=" "; 

      for(int i=0; i<l; i++) 
      { 
       ch = s.charAt(i); 
       if(ch!=' ') 
        ans = ans + ch; 
       s = s.replace(ch,' '); //Replacing all occurrence of the current character by a space 
      } 

      System.out.println("Word after removing duplicate characters : " + ans); 
     } 

} 

Answer 20

import java.util.Scanner; 

public class dublicate { 
    public static void main(String... a) { 
     System.out.print("Enter the String"); 
     Scanner Sc = new Scanner(System.in); 
     String st=Sc.nextLine(); 
     StringBuilder sb=new StringBuilder(); 
     boolean [] bc=new boolean[256]; 
     for(int i=0;i<st.length();i++) 
     { 
      int index=st.charAt(i); 
      if(bc[index]==false) 
      { 
       sb.append(st.charAt(i)); 
       bc[index]=true; 
      } 

     } 
     System.out.print(sb.toString()); 
    } 
} 

Answer 21

public static void main(String[] args) { 

    int i,j; 
    StringBuffer str=new StringBuffer(); 
    Scanner in = new Scanner(System.in); 
    System.out.print("Enter string: "); 

    str.append(in.nextLine()); 

    for (i=0;i<str.length()-1;i++) 
    { 
     for (j=1;j<str.length();j++) 
     { 
      if (str.charAt(i)==str.charAt(j)) 
       str.deleteCharAt(j); 
     } 
    } 
    System.out.println("Removed String: " + str); 
} 

Answer 22

Ésta es la mejora en la solución sugerida por @Dave. Aquí, estoy implementando en solo lazo único.

Let de reutilizar el retorno deset.add (T artículo) método y agregarlo al mismo tiempo en StringBuffer si es acertado complemento

Esto es sólo O (n). No es necesario hacer un bucle de nuevo.

String string = "aabbccdefatafaz"; 

char[] chars = string.toCharArray(); 
StringBuilder sb = new StringBuilder(); 
Set<Character> charSet = new LinkedHashSet<Character>(); 
for (char c : chars) { 
    if(charSet.add(c)){ 
     sb.append(c); 
    } 

} 
System.out.println(sb.toString()); // abcdeftz 

Answer 23

solución simple es iterar a través de la cadena y poner a cada carácter único dentro de otra (en este caso, una variable resultado) si esta cadena no contiene que character.Finally particular, volver resultado cadena como salida.

A continuación está el fragmento de código probado y probado para eliminar caracteres duplicados de la cadena dada que tiene una complejidad de tiempo O (n).

private static String removeDuplicate(String s) { 
     String result=""; 
     for (int i=0 ;i<s.length();i++) { 
      char ch = s.charAt(i); 
      if (!result.contains(""+ch)) { 
       result+=""+ch; 
      } 
     } 
     return result; 
    } 

Si la entrada es señora luego salida será loco.
Si la entrada es anagrama entonces la salida será angrm

Espero que esto ayude.
Gracias

Answer 24

Para la simplicidad del código- he tomado de entrada de hardcore, uno puede tomar la entrada mediante el uso de la clase escáner también

public class KillDuplicateCharInString { 
    public static void main(String args[]) { 
     String str= "aaaabccdde "; 
     char arr[]= str.toCharArray(); 
     int n = arr.length; 
     String finalStr=""; 
     for(int i=0;i<n;i++) { 
      if(i==n-1){ 
       finalStr+=arr[i]; 
       break; 
      } 
      if(arr[i]==arr[i+1]) { 
       continue; 
      } 
      else { 
       finalStr+=arr[i]; 
      } 
     } 
     System.out.println(finalStr); 



    } 
} 

Answer 25

Usando corriente hace que sea fácil.

import java.util.Arrays; 
import java.util.stream.Collectors; 

public class MyClass { 

    public static String removeDuplicates(String myString) { 
     return Arrays.asList(myString.split("")).stream().distinct().collect(Collectors.joining()); 
    } 
} 

Aquí es parte de la documentación más sobre Stream y todo lo que puede hacer con él : https://docs.oracle.com/javase/8/docs/api/java/util/stream/package-summary.html

La 'descripción' parte es muy instructiva sobre los beneficios de los arroyos.

Answer 26

public static void main (String[] args) 
{ 
    Scanner sc = new Scanner(System.in); 
    String s = sc.next(); 
    String str = ""; 
    char c; 
    for(int i = 0; i < s.length(); i++) 
    { 
     c = s.charAt(i); 
     str = str + c; 
     s = s.replace(c, ' '); 
     if(i == s.length() - 1) 
     { 
      System.out.println(str.replaceAll("\\s", "")); 
     } 
    } 
} 

Answer 27

package com.st.removeduplicate; 
public class RemoveDuplicate { 
    public static void main(String[] args) { 
    String str1="shushil",str2="";  
    for(int i=0; i<=str1.length()-1;i++) { 
     int count=0; 
     for(int j=0;j<=i;j++) { 
      if(str1.charAt(i)==str1.charAt(j)) 
       count++; 
      if(count >1) 
       break; 
     } 
     if(count==1) 
      str2=str2+str1.charAt(i); 
    } 
    System.out.println(str2); 

} 

}

Answer 28

A mí me parece que todo el mundo está tratando demasiado duro para realizar esta tarea. Todo lo que nos preocupa es que copia 1 copia de cada letra si se repite. Entonces, como nos preocupa que esos personajes se repitan uno tras otro, los bucles anidados se vuelven arbitrarios, ya que simplemente puede comparar la posición n con la posición n + 1. Entonces, como esto solo copia las cosas cuando son diferentes, resuelva el problema. último personaje, puede agregar espacios en blanco al final de la cadena original, o simplemente hacer que copie el último carácter de la cadena a su resultado.

cadena removeDuplicate (String s) {

String result = ""; 

    for (int i = 0; i < s.length(); i++){ 
     if (i + 1 < s.length() && s.charAt(i) != s.charAt(i+1)){ 
      result = result + s.charAt(i); 
     } 
     if (i + 1 == s.length()){ 
      result = result + s.charAt(i); 
     } 
    } 

    return result; 

}