Dada una string, busque todos los caracteres distintos (o caracteres que no se repiten) en ella. Por ejemplo, si la string de entrada es «Geeks for Geeks», la salida debería ser ‘for’ y si la string de entrada es «Geeks Quiz», la salida debería ser ‘GksQuiz’.
Los distintos caracteres deben imprimirse en el mismo orden en que aparecen en la string de entrada.
Ejemplos:
Input : Geeks for Geeks Output : for Input : Hello Geeks Output : HoGks
Método 1 (Simple: O(n 2 ))
Una solución simple es ejecutar dos bucles. Comience a atravesar desde el lado izquierdo. Para cada carácter, compruebe si se repite o no. Si el carácter no se repite, incremente el número de caracteres que no se repiten. Cuando el conteo sea 1, devuelva cada carácter.
C++
#include <bits/stdc++.h> using namespace std; int main() { string str = "GeeksforGeeks"; for (int i = 0; i < str.size(); i++) { int flag = 0; for (int j = 0; j < str.size(); j++) { // checking if two characters are equal if (str[i] == str[j] and i != j) { flag = 1; break; } } if (flag == 0) cout << str[i]; } return 0; } // This code is contributed by umadevi9616
Java
import java.util.*; class GFG{ public static void main(String[] args) { String str = "GeeksforGeeks"; for (int i = 0; i < str.length(); i++) { int flag = 0; for (int j = 0; j < str.length(); j++) { // checking if two characters are equal if (str.charAt(i) == str.charAt(j) && i != j) { flag = 1; break; } } if (flag == 0) System.out.print(str.charAt(i)); } } } // This code is contributed by gauravrajput1
Python3
string="GeeksforGeeks" for i in range(0,len(string)): flag=0 for j in range(0,len(string)): #checking if two characters are equal if(string[i]==string[j] and i!=j): flag=1 break if(flag==0): print(string[i],end="")
C#
using System; public class GFG{ public static void Main(String[] args) { String str = "GeeksforGeeks"; for (int i = 0; i < str.Length; i++) { int flag = 0; for (int j = 0; j < str.Length; j++) { // checking if two characters are equal if (str[i] == str[j] && i != j) { flag = 1; break; } } if (flag == 0) Console.Write(str[i]); } } } // This code is contributed by gauravrajput1
Javascript
<script> var str = "GeeksforGeeks"; for (var i = 0; i < str.length; i++) { var flag = 0; for (j = 0; j < str.length; j++) { // checking if two characters are equal if (str.charAt(i) == str.charAt(j) && i != j) { flag = 1; break; } } if (flag == 0) document.write(str.charAt(i)); } // This code is contributed by gauravrajput1 </script>
for
Tiempo Complejidad: O(n 2 )
Espacio Auxiliar: O(1)
Método 2 (Eficiente pero requiere dos recorridos: O(n))
- Cree una array count[] para almacenar recuentos de caracteres.
- Recorra la string de entrada str y haga lo siguiente para cada carácter x = str[i].
Cuenta de incrementos[x]. - Recorra la string de entrada nuevamente y haga lo siguiente para cada carácter str[i]
- Si count[x] es 1, imprima el carácter único
- Si count[x] es mayor que 1, ignore el carácter repetido.
A continuación se muestra la implementación de la idea anterior.
C++
// C++ program to print distinct characters of a // string. # include <iostream> using namespace std; # define NO_OF_CHARS 256 /* Print duplicates present in the passed string */ void printDistinct(char *str) { // Create an array of size 256 and count of // every character in it int count[NO_OF_CHARS]; /* Count array with frequency of characters */ int i; for (i = 0; *(str+i); i++) if(*(str+i)!=' ') count[*(str+i)]++; int n = i; // Print characters having count more than 0 for (i = 0; i < n; i++) if (count[*(str+i)] == 1) cout<< str[i]; } /* Driver program*/ int main() { char str[] = "GeeksforGeeks"; printDistinct(str); return 0; }
Java
// Java program to print distinct characters of a // string. public class GFG { static final int NO_OF_CHARS = 256; /* Print duplicates present in the passed string */ static void printDistinct(String str) { // Create an array of size 256 and count of // every character in it int[] count = new int[NO_OF_CHARS]; /* Count array with frequency of characters */ int i; for (i = 0; i < str.length(); i++) if(str.charAt(i)!=' ') count[(int)str.charAt(i)]++; int n = i; // Print characters having count more than 0 for (i = 0; i < n; i++) if (count[(int)str.charAt(i)] == 1) System.out.print(str.charAt(i)); } /* Driver program*/ public static void main(String args[]) { String str = "GeeksforGeeks"; printDistinct(str); } } // This code is contributed by Sumit Ghosh
Python3
# Python3 program to print distinct # characters of a string. NO_OF_CHARS = 256 # Print duplicates present in the # passed string def printDistinct(str): # Create an array of size 256 and # count of every character in it count = [0] * NO_OF_CHARS # Count array with frequency of # characters for i in range (len(str)): if(str[i] != ' '): count[ord(str[i])] += 1 n = i # Print characters having count # more than 0 for i in range(n): if (count[ord(str[i])] == 1): print (str[i], end = "") # Driver Code if __name__ == "__main__": str = "GeeksforGeeks" printDistinct(str) # This code is contributed by ita_c
C#
// C# program to print distinct characters // of a string. using System; public class GFG { static int NO_OF_CHARS = 256; /* Print duplicates present in the passed string */ static void printDistinct(String str) { // Create an array of size 256 and // count of every character in it int[] count = new int[NO_OF_CHARS]; /* Count array with frequency of characters */ int i; for (i = 0; i < str.Length; i++) if(str[i]!=' ') count[(int)str[i]]++; int n = i; // Print characters having count // more than 0 for (i = 0; i < n; i++) if (count[(int)str[i]] == 1) Console.Write(str[i]); } /* Driver program*/ public static void Main() { String str = "GeeksforGeeks"; printDistinct(str); } } // This code is contributed by parashar.
Javascript
<script> // Javascript program to print distinct characters of a // string. let NO_OF_CHARS = 256; /* Print duplicates present in the passed string */ function printDistinct(str) { // Create an array of size 256 and count of // every character in it let count = new Array(NO_OF_CHARS); for(let i=0;i<NO_OF_CHARS;i++) { count[i]=0; } /* Count array with frequency of characters */ let i; for (i = 0; i < str.length; i++) if(str[i]!=' ') count[str[i].charCodeAt(0)]++; let n = i; // Print characters having count more than 0 for (i = 0; i < n; i++) if (count[str[i].charCodeAt(0)] == 1) document.write(str[i]); } /* Driver program*/ let str = "GeeksforGeeks"; printDistinct(str); // This code is contributed by rag2127 </script>
Producción:
for
Complejidad temporal: O(n)
Espacio auxiliar: O(n)
Método 3 (O(n) y requiere un recorrido)
La idea es utilizar dos arrays auxiliares de tamaño 256 (suponiendo que los caracteres se almacenan utilizando 8 bits).
- Inicialice todos los valores en count[] como 0 y todos los valores en index[] como n donde n es la longitud de la string.
- Recorra la string de entrada str y haga lo siguiente para cada carácter c = str[i].
- Cuenta de incrementos[x].
- Si cuenta[x] es 1, entonces almacene el índice de x en índice[x], es decir, índice[x] = i
- Si count[x] es 2, entonces elimine x de index[], es decir, index[x] = n
- Ahora index[] tiene índices de todos los caracteres distintos. Ordene índices e imprima caracteres usándolo. Tenga en cuenta que este paso toma O (1) tiempo asumiendo que el número de caracteres es fijo (típicamente 256)
A continuación se muestra la implementación de la idea anterior.
C++
// C++ program to find all distinct characters // in a string #include <bits/stdc++.h> using namespace std; const int MAX_CHAR = 256; // Function to print distinct characters in // given string str[] void printDistinct(string str) { int n = str.length(); // count[x] is going to store count of // character 'x' in str. If x is not present, // then it is going to store 0. int count[MAX_CHAR]; // index[x] is going to store index of character // 'x' in str. If x is not present or x is // more than once, then it is going to store a value // (for example, length of string) that cannot be // a valid index in str[] int index[MAX_CHAR]; // Initialize counts of all characters and indexes // of distinct characters. for (int i = 0; i < MAX_CHAR; i++) { count[i] = 0; index[i] = n; // A value more than any index // in str[] } // Traverse the input string for (int i = 0; i < n; i++) { // Find current character and increment its // count char x = str[i]; ++count[x]; // If this is first occurrence, then set value // in index as index of it. if (count[x] == 1 && x !=' ') index[x] = i; // If character repeats, then remove it from // index[] if (count[x] == 2) index[x] = n; } // Since size of index is constant, below operations // take constant time. sort(index, index+MAX_CHAR); for (int i=0; i<MAX_CHAR && index[i] != n; i++) cout << str[index[i]]; } // Driver code int main() { string str = "GeeksforGeeks"; printDistinct(str); return 0; }
Java
// Java program to print distinct characters of // a string. import java.util.Arrays; public class GFG { static final int MAX_CHAR = 256; // Function to print distinct characters in // given string str[] static void printDistinct(String str) { int n = str.length(); // count[x] is going to store count of // character 'x' in str. If x is not present, // then it is going to store 0. int[] count = new int[MAX_CHAR]; // index[x] is going to store index of character // 'x' in str. If x is not present or x is // more than once, then it is going to store a // value (for example, length of string) that // cannot be a valid index in str[] int[] index = new int[MAX_CHAR]; // Initialize counts of all characters and // indexes of distinct characters. for (int i = 0; i < MAX_CHAR; i++) { count[i] = 0; index[i] = n; // A value more than any // index in str[] } // Traverse the input string for (int i = 0; i < n; i++) { // Find current character and increment // its count char x = str.charAt(i); ++count[x]; // If this is first occurrence, then set // value in index as index of it. if (count[x] == 1 && x !=' ') index[x] = i; // If character repeats, then remove it // from index[] if (count[x] == 2) index[x] = n; } // Since size of index is constant, below // operations take constant time. Arrays.sort(index); for (int i = 0; i < MAX_CHAR && index[i] != n; i++) System.out.print(str.charAt(index[i])); } // Driver code public static void main(String args[]) { String str = "GeeksforGeeks"; printDistinct(str); } } // This code is contributed by Sumit Ghosh
Python
# Python3 program to find all distinct characters # in a String MAX_CHAR = 256 # Function to print distinct characters in # given Str[] def printDistinct(Str): n = len(Str) # count[x] is going to store count of # character 'x' in Str. If x is not present, # then it is going to store 0. count = [0 for i in range(MAX_CHAR)] # index[x] is going to store index of character # 'x' in Str. If x is not present or x is # more than once, then it is going to store a value # (for example, length of String) that cannot be # a valid index in Str[] index = [n for i in range(MAX_CHAR)] # Traverse the input String for i in range(n): # Find current character and increment its # count x = ord(Str[i]) count[x] += 1 # If this is first occurrence, then set value # in index as index of it. if (count[x] == 1 and x !=' '): index[x] = i # If character repeats, then remove it from # index[] if (count[x] == 2): index[x] = n # Since size of index is constant, below operations # take constant time. index=sorted(index) for i in range(MAX_CHAR): if index[i] == n: break print(Str[index[i]],end="") # Driver code Str = "GeeksforGeeks" printDistinct(Str) # This code is contributed by mohit kumar 29
C#
// C# program to print distinct characters of // a string. using System; public class GFG { static int MAX_CHAR = 256; // Function to print distinct characters in // given string str[] static void printDistinct(string str) { int n = str.Length; // count[x] is going to store count of // character 'x' in str. If x is not // present, then it is going to store 0. int []count = new int[MAX_CHAR]; // index[x] is going to store index of // character 'x' in str. If x is not // present or x is more than once, then // it is going to store a value (for // example, length of string) that // cannot be a valid index in str[] int []index = new int[MAX_CHAR]; // Initialize counts of all characters // and indexes of distinct characters. for (int i = 0; i < MAX_CHAR; i++) { count[i] = 0; // A value more than any index // in str[] index[i] = n; } // Traverse the input string for (int i = 0; i < n; i++) { // Find current character and // increment its count char x = str[i]; ++count[x]; // If this is first occurrence, then // set value in index as index of it. if (count[x] == 1 && x !=' ') index[x] = i; // If character repeats, then remove // it from index[] if (count[x] == 2) index[x] = n; } // Since size of index is constant, below // operations take constant time. Array.Sort(index); for (int i = 0; i < MAX_CHAR && index[i] != n; i++) Console.Write(str[index[i]]); } // Driver code public static void Main() { string str = "GeeksforGeeks"; printDistinct(str); } } // This code is contributed by nitin mittal.
Javascript
<script> // Javascript program to print distinct characters of // a string. let MAX_CHAR = 256; // Function to print distinct characters in // given string str[] function printDistinct(str) { let n = str.length; // count[x] is going to store count of // character 'x' in str. If x is not present, // then it is going to store 0. let count = new Array(MAX_CHAR); // index[x] is going to store index of character // 'x' in str. If x is not present or x is // more than once, then it is going to store a // value (for example, length of string) that // cannot be a valid index in str[] let index = new Array(MAX_CHAR); // Initialize counts of all characters and // indexes of distinct characters. for (let i = 0; i < MAX_CHAR; i++) { count[i] = 0; index[i] = n; // A value more than any // index in str[] } // Traverse the input string for (let i = 0; i < n; i++) { // Find current character and increment // its count let x = str[i].charCodeAt(0); ++count[x]; // If this is first occurrence, then set // value in index as index of it. if (count[x] == 1 && x !=' ') index[x] = i; // If character repeats, then remove it // from index[] if (count[x] == 2) index[x] = n; } // Since size of index is constant, below // operations take constant time. index.sort(function(a,b){return a-b}); for (let i = 0; i < MAX_CHAR && index[i] != n; i++) document.write(str[index[i]]); } // Driver code let str = "GeeksforGeeks"; printDistinct(str); // This code is contributed by avanitrachhadiya2155 </script>
for
Complejidad temporal: O(n)
Espacio auxiliar: O(n)
Este artículo es una contribución de Aarti_Rathi y Afzal Ansari . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su 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.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA