Dada una string, determine si la string tiene todos los caracteres únicos.
Ejemplos:
Input : abcd10jk Output : true Input : hutg9mnd!nk9 Output : false
Enfoque 1: técnica de fuerza bruta : ejecute 2 bucles con las variables i y j. Compare str[i] y str[j]. Si se vuelven iguales en algún punto, devuelve falso.
C++
// C++ program to illustrate string // with unique characters using // brute force technique #include <bits/stdc++.h> using namespace std; bool uniqueCharacters(string str) { // If at any time we encounter 2 // same characters, return false for (int i = 0; i < str.length() - 1; i++) { for (int j = i + 1; j < str.length(); j++) { if (str[i] == str[j]) { return false; } } } // If no duplicate characters encountered, // return true return true; } // driver code int main() { string str = "GeeksforGeeks"; if (uniqueCharacters(str)) { cout << "The String " << str << " has all unique characters\n"; } else { cout << "The String " << str << " has duplicate characters\n"; } return 0; } // This code is contributed by Divyam Madaan
Java
// Java program to illustrate string with // unique characters using brute force technique import java.util.*; class GfG { boolean uniqueCharacters(String str) { // If at any time we encounter 2 same // characters, return false for (int i = 0; i < str.length(); i++) for (int j = i + 1; j < str.length(); j++) if (str.charAt(i) == str.charAt(j)) return false; // If no duplicate characters encountered, // return true return true; } public static void main(String args[]) { GfG obj = new GfG(); String input = "GeeksforGeeks"; if (obj.uniqueCharacters(input)) System.out.println("The String " + input + " has all unique characters"); else System.out.println("The String " + input + " has duplicate characters"); } }
Python3
# Python program to illustrate string # with unique characters using # brute force technique def uniqueCharacters(str): # If at any time we encounter 2 # same characters, return false for i in range(len(str)): for j in range(i + 1,len(str)): if(str[i] == str[j]): return False; # If no duplicate characters # encountered, return true return True; # Driver Code str = "GeeksforGeeks"; if(uniqueCharacters(str)): print("The String ", str," has all unique characters"); else: print("The String ", str, " has duplicate characters"); # This code contributed by PrinciRaj1992
C#
// C# program to illustrate string with // unique characters using brute force // technique using System; public class GFG { static bool uniqueCharacters(String str) { // If at any time we encounter 2 // same characters, return false for (int i = 0; i < str.Length; i++) for (int j = i + 1; j < str.Length; j++) if (str[i] == str[j]) return false; // If no duplicate characters // encountered, return true return true; } public static void Main() { string input = "GeeksforGeeks"; if (uniqueCharacters(input) == true) Console.WriteLine("The String " + input + " has all unique characters"); else Console.WriteLine("The String " + input + " has duplicate characters"); } } // This code is contributed by shiv_bhakt.
PHP
<?php // PHP program to illustrate string // with unique characters using // brute force technique function uniqueCharacters($str) { // If at any time we encounter 2 // same characters, return false for($i = 0; $i < strlen($str); $i++) { for($j = $i + 1; $j < strlen($str); $j++) { if($str[$i] == $str[$j]) { return false; } } } // If no duplicate characters // encountered, return true return true; } // Driver Code $str = "GeeksforGeeks"; if(uniqueCharacters($str)) { echo "The String ", $str, " has all unique characters\n"; } else { echo "The String ", $str, " has duplicate characters\n"; } // This code is contributed by ajit ?>
Javascript
<script> // Javascript program to illustrate string with // unique characters using brute force // technique function uniqueCharacters(str) { // If at any time we encounter 2 // same characters, return false for(let i = 0; i < str.length; i++) for(let j = i + 1; j < str.length; j++) if (str[i] == str[j]) return false; // If no duplicate characters // encountered, return true return true; } // Driver code let input = "GeeksforGeeks"; if (uniqueCharacters(input) == true) document.write("The String " + input + " has all unique characters" + "</br>"); else document.write("The String " + input + " has duplicate characters"); // This code is contributed by decode2207 </script>
Producción :
The String GeeksforGeeks has duplicate characters
Tiempo Complejidad : O(n 2 )
Espacio auxiliar: O(1)
Nota: Tenga en cuenta que el programa distingue entre mayúsculas y minúsculas.
Enfoque 2: clasificación : uso de clasificación basada en valores ASCII de caracteres
C++
// C++ program to illustrate string // with unique characters using // brute force technique #include <bits/stdc++.h> using namespace std; bool uniqueCharacters(string str) { // Using sorting sort(str.begin(), str.end()); for (int i = 0; i < str.length()-1; i++) { // if at any time, 2 adjacent // elements become equal, // return false if (str[i] == str[i + 1]) { return false; } } return true; } // driver code int main() { string str = "GeeksforGeeks"; if (uniqueCharacters(str)) { cout << "The String " << str << " has all unique characters\n"; } else { cout << "The String " << str << " has duplicate characters\n"; } return 0; } // This code is contributed by Divyam Madaan
Java
// Java program to check string with unique // characters using sorting technique import java.util.*; class GfG { /* Convert the string to character array for sorting */ boolean uniqueCharacters(String str) { char[] chArray = str.toCharArray(); // Using sorting // Arrays.sort() uses binarySort in the background // for non-primitives which is of O(nlogn) time complexity Arrays.sort(chArray); for (int i = 0; i < chArray.length - 1; i++) { // if the adjacent elements are not // equal, move to next element if (chArray[i] != chArray[i + 1]) continue; // if at any time, 2 adjacent elements // become equal, return false else return false; } return true; } // Driver code public static void main(String args[]) { GfG obj = new GfG(); String input = "GeeksforGeeks"; if (obj.uniqueCharacters(input)) System.out.println("The String " + input + " has all unique characters"); else System.out.println("The String " + input + " has duplicate characters"); } }
Python3
# Python3 program to illustrate string # with unique characters using # brute force technique def uniqueCharacters(st): # Using sorting st = sorted(st) for i in range(len(st)-1): # if at any time, 2 adjacent # elements become equal, # return false if (st[i] == st[i + 1]) : return False return True # Driver code if __name__=='__main__': st = "GeeksforGeeks" if (uniqueCharacters(st)) : print("The String",st,"has all unique characters\n") else : print("The String",st,"has duplicate characters\n") # This code is contributed by AbhiThakur
C#
// C# program to check string with unique // characters using sorting technique using System; public class GFG { /* Convert the string to character array for sorting */ static bool uniqueCharacters(String str) { char[] chArray = str.ToCharArray(); // Using sorting Array.Sort(chArray); for (int i = 0; i < chArray.Length - 1; i++) { // if the adjacent elements are not // equal, move to next element if (chArray[i] != chArray[i + 1]) continue; // if at any time, 2 adjacent elements // become equal, return false else return false; } return true; } // Driver code public static void Main() { string input = "GeeksforGeeks"; if (uniqueCharacters(input) == true) Console.WriteLine("The String " + input + " has all unique characters"); else Console.WriteLine("The String " + input + " has duplicate characters"); } } // This code is contributed by shiv_bhakt.
Javascript
<script> // Javascript program to // check string with unique // characters using sorting technique /* Convert the string to character array for sorting */ function uniqueCharacters(str) { let chArray = str.split(''); // Using sorting chArray.sort(); for (let i = 0; i < chArray.length - 1; i++) { // if the adjacent elements are not // equal, move to next element if (chArray[i] != chArray[i + 1]) continue; // if at any time, 2 adjacent elements // become equal, return false else return false; } return true; } let input = "GeeksforGeeks"; if (uniqueCharacters(input) == true) document.write("The String " + input + " has all unique characters" + "</br>"); else document.write("The String " + input + " has duplicate characters" + "</br>"); </script>
Producción:
The String GeeksforGeeks has duplicate characters
Complejidad de tiempo : O (nlogn)
Espacio Auxiliar: O(1)
Enfoque 3: uso de una estructura de datos adicional : este enfoque asume un conjunto de caracteres ASCII (8 bits). La idea es mantener una array booleana para los caracteres. Los 256 índices representan 256 caracteres. Todos los elementos de la array se establecen inicialmente en falso. A medida que iteramos sobre la string, establezca verdadero en el índice igual al valor int del carácter. Si en algún momento nos encontramos con que el valor de la array ya es verdadero, significa que el carácter con ese valor int se repite.
C++
#include <cstring> #include <iostream> using namespace std; const int MAX_CHAR = 256; bool uniqueCharacters(string str) { // If length is greater than 265, // some characters must have been repeated if (str.length() > MAX_CHAR) return false; bool chars[MAX_CHAR] = { 0 }; for (int i = 0; i < str.length(); i++) { if (chars[int(str[i])] == true) return false; chars[int(str[i])] = true; } return true; } // driver code int main() { string str = "GeeksforGeeks"; if (uniqueCharacters(str)) { cout << "The String " << str << " has all unique characters\n"; } else { cout << "The String " << str << " has duplicate characters\n"; } return 0; } // This code is contributed by Divyam Madaan
Java
// Java program to illustrate String With // Unique Characters using data structure import java.util.*; class GfG { int MAX_CHAR = 256; boolean uniqueCharacters(String str) { // If length is greater than 256, // some characters must have been repeated if (str.length() > MAX_CHAR) return false; boolean[] chars = new boolean[MAX_CHAR]; Arrays.fill(chars, false); for (int i = 0; i < str.length(); i++) { int index = (int)str.charAt(i); /* If the value is already true, string has duplicate characters, return false */ if (chars[index] == true) return false; chars[index] = true; } /* No duplicates encountered, return true */ return true; } // Driver code public static void main(String args[]) { GfG obj = new GfG(); String input = "GeeksforGeeks"; if (obj.uniqueCharacters(input)) System.out.println("The String " + input + " has all unique characters"); else System.out.println("The String " + input + " has duplicate characters"); } }
Python3
# Python program to illustrate # string with unique characters # using data structure MAX_CHAR = 256; def uniqueCharacters(string): n = len(string) # If length is greater than 256, # some characters must have # been repeated if n > MAX_CHAR: return False chars = [False] * MAX_CHAR for i in range(n): index = ord(string[i]) ''' * If the value is already True, string has duplicate characters, return False''' if (chars[index] == True): return False chars[index] = True ''' No duplicates encountered, return True ''' return True # Driver code if __name__ == '__main__': input = "GeeksforGeeks" if (uniqueCharacters(input)): print("The String", input, "has all unique characters") else: print("The String", input, "has duplicate characters") # This code is contributed by shikhasingrajput
C#
// C# program to illustrate String With // Unique Characters using data structure using System; class GfG { static int MAX_CHAR = 256; bool uniqueCharacters(String str) { // If length is greater than 256, // some characters must have been repeated if (str.Length > MAX_CHAR) return false; bool[] chars = new bool[MAX_CHAR]; for (int i = 0; i < MAX_CHAR; i++) { chars[i] = false; } for (int i = 0; i < str.Length; i++) { int index = (int)str[i]; /* If the value is already true, string has duplicate characters, return false */ if (chars[index] == true) return false; chars[index] = true; } /* No duplicates encountered, return true */ return true; } // Driver code public static void Main(String[] args) { GfG obj = new GfG(); String input = "GeeksforGeeks"; if (obj.uniqueCharacters(input)) Console.WriteLine("The String " + input + " has all unique characters"); else Console.WriteLine("The String " + input + " has duplicate characters"); } } // This code has been contributed by 29AjayKumar
Javascript
<script> // Javascript program to illustrate String With // Unique Characters using data structure let MAX_CHAR = 256; function uniqueCharacters(str) { // If length is greater than 256, // some characters must have been repeated if (str.length > MAX_CHAR) return false; let chars = new Array(MAX_CHAR); for (let i = 0; i < MAX_CHAR; i++) { chars[i] = false; } for (let i = 0; i < str.length; i++) { let index = str[i].charCodeAt(); /* If the value is already true, string has duplicate characters, return false */ if (chars[index] == true) return false; chars[index] = true; } /* No duplicates encountered, return true */ return true; } let input = "GeeksforGeeks"; if (uniqueCharacters(input)) document.write("The String " + input + " has all unique characters"); else document.write("The String " + input + " has duplicate characters"); </script>
Producción:
The String GeeksforGeeks has duplicate characters
Complejidad de tiempo : O(n)
Espacio Auxiliar: O(n)
Enfoque 4: sin estructura de datos adicional: el enfoque es válido para strings que tienen el alfabeto como az. Este enfoque es un poco complicado. En lugar de mantener una array booleana, mantenemos un valor entero llamado verificador (32 bits). A medida que iteramos sobre la string, encontramos el valor int del carácter con respecto a ‘a’ con la instrucción int bitAtIndex = str.charAt(i)-‘a’;
Luego, el bit en ese valor int se establece en 1 con la instrucción 1 << bitAtIndex .
Ahora, si este bit ya está establecido en el verificador, la operación AND del bit haría que el verificador > 0. Devuelva falso en este caso.
De lo contrario, actualice el verificador para hacer que el bit 1 en ese índice con la declaración verificador = verificador | (1 <<bitAtIndex);
C++
// C++ program to illustrate string // with unique characters using // brute force technique #include <bits/stdc++.h> using namespace std; bool uniqueCharacters(string str) { // Assuming string can have characters // a-z, this has 32 bits set to 0 int checker = 0; for (int i = 0; i < str.length(); i++) { int bitAtIndex = str[i] - 'a'; // if that bit is already set in // checker, return false if ((checker & (1 << bitAtIndex)) > 0) { return false; } // otherwise update and continue by // setting that bit in the checker checker = checker | (1 << bitAtIndex); } // no duplicates encountered, return true return true; } // driver code int main() { string str = "geeksforgeeks"; if (uniqueCharacters(str)) { cout << "The String " << str << " has all unique characters\n"; } else { cout << "The String " << str << " has duplicate characters\n"; } return 0; } // This code is contributed by Divyam Madaan
Java
// Java program to illustrate String with unique // characters without using any data structure import java.util.*; class GfG { boolean uniqueCharacters(String str) { // Assuming string can have characters a-z // this has 32 bits set to 0 int checker = 0; for (int i = 0; i < str.length(); i++) { int bitAtIndex = str.charAt(i) - 'a'; // if that bit is already set in checker, // return false if ((checker & (1 << bitAtIndex)) > 0) return false; // otherwise update and continue by // setting that bit in the checker checker = checker | (1 << bitAtIndex); } // no duplicates encountered, return true return true; } // Driver Code public static void main(String args[]) { GfG obj = new GfG(); String input = "geekforgeeks"; if (obj.uniqueCharacters(input)) System.out.println("The String " + input + " has all unique characters"); else System.out.println("The String " + input + " has duplicate characters"); } }
Python3
# Python3 program to illustrate String with unique # characters without using any data structure import math def uniqueCharacters(string): # Assuming string can have characters # a-z this has 32 bits set to 0 checker = 0 for i in range(len(string)): bitAtIndex = ord(string[i]) - ord('a') # If that bit is already set in # checker, return False if ((bitAtIndex) > 0): if ((checker & ((1 << bitAtIndex))) > 0): return False # Otherwise update and continue by # setting that bit in the checker checker = checker | (1 << bitAtIndex) # No duplicates encountered, return True return True # Driver Code if __name__ == '__main__': input = "geekforgeeks" if (uniqueCharacters(input)): print("The String " + input + " has all unique characters") else: print("The String " + input + " has duplicate characters") # This code is contributed by Princi Singh
C#
// C# program to illustrate String // with unique characters without // using any data structure using System; class GFG { public virtual bool uniqueCharacters(string str) { // Assuming string can have // characters a-z this has // 32 bits set to 0 int checker = 0; for (int i = 0; i < str.Length; i++) { int bitAtIndex = str[i] - 'a'; // if that bit is already set // in checker, return false if ((checker & (1 << bitAtIndex)) > 0) { return false; } // otherwise update and continue by // setting that bit in the checker checker = checker | (1 << bitAtIndex); } // no duplicates encountered, // return true return true; } // Driver Code public static void Main(string[] args) { GFG obj = new GFG(); string input = "geekforgeeks"; if (obj.uniqueCharacters(input)) { Console.WriteLine("The String " + input + " has all unique characters"); } else { Console.WriteLine("The String " + input + " has duplicate characters"); } } } // This code is contributed by Shrikant13
PHP
<?php // PHP program to illustrate // string with unique characters // using brute force technique function uniqueCharacters($str) { // Assuming string can have // characters a-z, this has // 32 bits set to 0 $checker = 0; for ($i = 0; $i < strlen($str); $i++) { $bitAtIndex = $str[$i] - 'a'; // if that bit is already set // in checker, return false if (($checker & (1 << $bitAtIndex)) > 0) { return false; } // otherwise update and continue by // setting that bit in the checker $checker = $checker | (1 << $bitAtIndex); } // no duplicates encountered, // return true return true; } // Driver Code $str = "geeksforgeeks"; if(uniqueCharacters($str)) { echo "The String ", $str, " has all unique characters\n"; } else { echo "The String ", $str, " has duplicate characters\n"; } // This code is contributed by ajit ?>
Javascript
<script> // Javascript program to illustrate String // with unique characters without // using any data structure function uniqueCharacters(str) { // Assuming string can have // characters a-z this has // 32 bits set to 0 let checker = 0; for (let i = 0; i < str.length; i++) { let bitAtIndex = str[i].charCodeAt(0) - 'a'.charCodeAt(0); // if that bit is already set // in checker, return false if ((checker & (1 << bitAtIndex)) > 0) { return false; } // otherwise update and continue by // setting that bit in the checker checker = checker | (1 << bitAtIndex); } // no duplicates encountered, // return true return true; } let input = "geekforgeeks"; if (uniqueCharacters(input)) { document.write("The String " + input + " has all unique characters"); } else { document.write("The String " + input + " has duplicate characters"); } </script>
Producción :
The String GeekforGeeks has duplicate characters
Complejidad de tiempo : O(n)
Espacio Auxiliar: O(1)
Ejercicio: el programa anterior no distingue entre mayúsculas y minúsculas, puede intentar hacer el mismo programa que distingue entre mayúsculas y minúsculas, es decir, Geeks y GEeks dan resultados diferentes.
Usando flujo de Java :
Java
import java.util.Collections; import java.util.stream.Collectors; class GfG { boolean uniqueCharacters(String s) { // If at any character more than once create another stream // stream count more than 0, return false return s.chars().filter(e-> Collections.frequency(s.chars().boxed().collect(Collectors.toList()), e) > 1).count() > 1 ? false: true; } public static void main(String args[]) { GfG obj = new GfG(); String input = "GeeksforGeeks"; if (obj.uniqueCharacters(input)) System.out.println("The String " + input + " has all unique characters"); else System.out.println("The String " + input + " has duplicate characters"); } } //Write Java code here
Python3
# Python3 program to implement the approach from collections import Counter def uniqueCharacters(s): # If at any character more than once create another stream # stream count more than 0, return false return not any(filter(lambda x: x > 1, list(Counter(list(s)).values()))) # Driver code input = "GeeksforGeeks" if uniqueCharacters(input): print("The String " + input + " has all unique characters") else: print("The String " + input + " has duplicate characters") # This code is contributed by phasing17
Javascript
// JavaScript code to implement the approach function uniqueCharacters(s) { // If at any character more than once create another // stream stream count more than 0, return false let arr = s.split(""); return !arr.some((v, i) => arr.indexOf(v) < i); } let input = "GeeksforGeeks"; if (uniqueCharacters(input)) console.log("The String " + input + " has all unique characters"); else console.log("The String " + input + " has duplicate characters"); // This code is contributed by phasing17
Referencia:
Entrevista de Cracking the Coding por Gayle
Enfoque 5: Uso de la función sets():
- Convierte la string a set.
- Si la longitud del conjunto es igual a la longitud de la string, devuelva True o False.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program to illustrate String with unique // characters using set data structure #include <bits/stdc++.h> using namespace std; bool uniqueCharacters(string str) { set<char> char_set; // Inserting character of string into set for(char c : str) { char_set.insert(c); } // If length of set is equal to len of string // then it will have unique characters return char_set.size() == str.size(); } // Driver code int main() { string str = "GeeksforGeeks"; if (uniqueCharacters(str)) { cout << "The String " << str << " has all unique characters\n"; } else { cout << "The String " << str << " has duplicate characters\n"; } return 0; } // This code is contributed by abhishekjha558498
Java
// Java program to illustrate String with unique // characters using set data structure import java.util.*; class GFG{ static boolean uniqueCharacters(String str) { HashSet<Character> char_set = new HashSet<>(); // Inserting character of String into set for(int c = 0; c< str.length();c++) { char_set.add(str.charAt(c)); } // If length of set is equal to len of String // then it will have unique characters return char_set.size() == str.length(); } // Driver code public static void main(String[] args) { String str = "GeeksforGeeks"; if (uniqueCharacters(str)) { System.out.print("The String " + str + " has all unique characters\n"); } else { System.out.print("The String " + str + " has duplicate characters\n"); } } } // This code contributed by umadevi9616
Python3
# Python3 program to illustrate String with unique # characters def uniqueCharacters(str): # Converting string to set setstring = set(str) # If length of set is equal to len of string # then it will have unique characters if(len(setstring) == len(str)): return True return False # Driver Code if __name__ == '__main__': input = "GeeksforGeeks" if (uniqueCharacters(input)): print("The String " + input + " has all unique characters") else: print("The String " + input + " has duplicate characters") # This code is contributed by vikkycirus
C#
// C# program to illustrate String with unique // characters using set data structure using System; using System.Collections.Generic; public class GFG { static bool uniquechars(String str) { HashSet<char> char_set = new HashSet<char>(); // Inserting character of String into set for (int c = 0; c < str.Length; c++) { char_set.Add(str); } // If length of set is equal to len of String // then it will have unique characters if (char_set.Count == str.Length) { return true; } else { return false; } } // Driver code public static void Main(String[] args) { String str = "GeeksforGeeks"; if (uniquechars(str)) { Console.Write("The String " + str + " has all unique characters\n"); } else { Console.Write("The String " + str + " has duplicate characters\n"); } } } // This code is contributed by umadevi9616
Javascript
<script> // Function program to illustrate String // with unique characters function uniqueCharacters(str) { // Converting string to set var setstring = new Set(str) // If length of set is equal to len of string // then it will have unique characters if (setstring.size == str.length) { return true } else { return false } } // Driver Code var input = "GeeksforGeeks" if (uniqueCharacters(input)) { document.write("The String " + input + " has all unique characters") ; } else { document.write("The String " + input + " has duplicate characters") } // This code is contributed by bunnyram19 </script>
Producción:
The String GeeksforGeeks has duplicate characters
Complejidad de tiempo: O (nlogn)
Espacio Auxiliar: O(n)
Este artículo es una contribución de Saloni Baweja . 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 contribuido@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