Implemente un algoritmo de espacio eficiente para determinar si una string (de caracteres de ‘a’ a ‘z’) tiene todos los caracteres únicos o no. No se permite el uso de estructuras de datos adicionales como array de conteo, hash, etc.
Complejidad de tiempo esperada: O (n)
Ejemplos:
Input : str = "aaabbccdaa" Output : No Input : str = "abcd" Output : Yes
La idea es usar una variable entera y usar bits en su representación binaria para almacenar si un carácter está presente o no. Por lo general, un número entero tiene al menos 32 bits y necesitamos almacenar presencia/ausencia de solo 26 caracteres.
A continuación se muestra la implementación de la idea.
C++
// A space efficient C++ program to check if
// all characters of string are unique.
#include<bits/stdc++.h>
using namespace std;
// Returns true if all characters of str are
// unique.
// Assumptions : (1) str contains only characters
// from 'a' to 'z'
// (2) integers are stored using 32
// bits
bool areChractersUnique(string str)
{
// An integer to store presence/absence
// of 26 characters using its 32 bits.
int checker = 0;
for (int i = 0; i < str.length(); ++i)
{
int val = (str[i]-'a');
// If bit corresponding to current
// character is already set
if ((checker & (1 << val)) > 0)
return false;
// set bit in checker
checker |= (1 << val);
}
return true;
}
// Driver code
int main()
{
string s = "aaabbccdaa";
if (areChractersUnique(s))
cout << "Yes";
else
cout << "No";
return 0;
}
Java
// A space efficient Java program to check if
// all characters of string are unique.
class GFG {
// Returns true if all characters of str are
// unique.
// Assumptions : (1) str contains only characters
// from 'a' to 'z'
// (2) integers are stored using 32
// bits
static boolean areChractersUnique(String str)
{
// An integer to store presence/absence
// of 26 characters using its 32 bits.
int checker = 0;
for (int i = 0; i < str.length(); ++i)
{
int val = (str.charAt(i)-'a');
// If bit corresponding to current
// character is already set
if ((checker & (1 << val)) > 0)
return false;
// set bit in checker
checker |= (1 << val);
}
return true;
}
//driver code
public static void main (String[] args)
{
String s = "aaabbccdaa";
if (areChractersUnique(s))
System.out.print("Yes");
else
System.out.print("No");
}
}
// This code is contributed by Anant Agarwal.
Python3
# A space efficient Python3 program to check if
# all characters of string are unique
# Returns true if all characters of str are
# unique.
# Assumptions : (1) str contains only characters
# from 'a' to 'z'
# (2) integers are stored using 32
# bits
def areCharactersUnique(s):
# An integer to store presence/absence
# of 26 characters using its 32 bits
checker = 0
for i in range(len(s)):
val = ord(s[i]) - ord('a')
# If bit corresponding to current
# character is already set
if (checker & (1 << val)) > 0:
return False
# set bit in checker
checker |= (1 << val)
return True
# Driver code
s = "aaabbccdaa"
if areCharactersUnique(s):
print("Yes")
else:
print("No")
# This code is contributed
# by Mohit Kumar
C#
// A space efficient program
// to check if all characters
// of string are unique.
using System;
class GFG {
// Returns true if all characters
// of str are unique. Assumptions:
// (1)str contains only characters
// from 'a' to 'z'.(2)integers are
// stored using 32 bits
static bool areChractersUnique(string str)
{
// An integer to store presence
// or absence of 26 characters
// using its 32 bits.
int checker = 0;
for (int i = 0; i < str.Length; ++i) {
int val = (str[i] - 'a');
// If bit corresponding to current
// character is already set
if ((checker & (1 << val)) > 0)
return false;
// set bit in checker
checker |= (1 << val);
}
return true;
}
// Driver code
public static void Main()
{
string s = "aaabbccdaa";
if (areChractersUnique(s))
Console.Write("Yes");
else
Console.Write("No");
}
}
// This code is contributed by Anant Agarwal.
PHP
<?php
// A space efficient PHP program
// to check if all characters of
// string are unique.
// Returns true if all characters
// of str are unique.
// Assumptions : (1) str contains
// only characters
// from 'a' to 'z'
// (2) integers are stored
// using 32 bits
function areChractersUnique($str)
{
// An integer to store presence/absence
// of 26 characters using its 32 bits.
$checker = 0;
for ($i = 0; $i < $len = strlen($str); ++$i)
{
$val = ($str[$i] - 'a');
// If bit corresponding to current
// character is already set
if (($checker & (1 << $val)) > 0)
return false;
// set bit in checker
$checker |= (1 << $val);
}
return true;
}
// Driver code
$s = "aaabbccdaa";
if (areChractersUnique($s))
echo "Yes";
else
echo "No";
// This code is contributed by aj_36
?>
Javascript
<script>
// Javascript program for the above approach
// Returns true if all characters of str are
// unique.
// Assumptions : (1) str contains only characters
// from 'a' to 'z'
// (2) integers are stored using 32
// bits
function areChractersUnique(str)
{
// An integer to store presence/absence
// of 26 characters using its 32 bits.
let checker = 0;
for (let i = 0; i < str.length; ++i)
{
let val = (str[i]-'a');
// If bit corresponding to current
// character is already set
if ((checker & (1 << val)) > 0)
return false;
// set bit in checker
checker |= (1 << val);
}
return true;
}
// Driver Code
var s = "aaabbccdaa";
if (areChractersUnique(s))
document.write("Yes");
else
document.write("No");
</script>
Producción
No
Tiempo Complejidad : O(n)
Espacio Auxiliar : O(1)
Otra implementación: uso de STL
C++
#include <bits/stdc++.h>
using namespace std;
bool unique(string s) {
sort(s.begin(),s.end());
for(int i=0;i<s.size()-1;i++)
{
if(s[i]==s[i+1])
{
return false;
break;
}
}
return true;
}
int main() {
if(unique("abcdd")==true)
{
cout <<"String is Unique"<<endl;
}
else
{
cout <<"String is not Unique"<<endl;
}
return 0;
}
Java
import java.util.Arrays;
class GFG {
static boolean unique(String s)
{
Arrays.sort(s.toCharArray());
for (int i = 0; i < s.length()-1; i++) {
if (s.charAt(i) == s.charAt(i + 1)) {
return false;
}
}
return true;
}
public static void main(String[] args)
{
if (unique("abcdd") == true) {
System.out.println("String is Unique");
}
else {
System.out.println("String is not Unique");
}
}
}
// This code is contributed by rajsanghavi9.
Python3
def unique(s):
s = list(s)
s.sort()
for i in range (len(s) - 1):
if(s[i] == s[i + 1]):
return False
break
return True
if(unique("abcdd") == True):
print("String is Unique")
else:
print("String is not Unique")
# This code is contributed by shivanisinghss2110
C#
using System;
public class GFG {
static bool unique(String s) {
Array.Sort(s.ToCharArray());
for (int i = 0; i < s.Length-1; i++) {
if (s[i] == s[i + 1]) {
return false;
}
}
return true;
}
// Driver code
public static void Main(String[] args) {
if (unique("abcdd") == true) {
Console.WriteLine("String is Unique");
} else {
Console.WriteLine("String is not Unique");
}
}
}
// This code is contributed by umadevi9616
Javascript
<script>
function unique(s) {
for (var i = 0; i < s.length-1; i++) {
if (s.charAt(i) == s.charAt(i + 1)) {
return false;
}
}
return true;
}
if (unique("abcdd") == true) {
document.write("String is Unique");
} else {
document.write("String is not Unique");
}
// This code is contributed by umadevi9616.
</script>
Producción
String is not Unique
Complejidad de tiempo: O (nlogn), donde n es la longitud de la string dada.
Espacio auxiliar: O(1), no se requiere espacio extra por lo que es una constante.
Este artículo es una contribución del Sr. Somesh Awasthi . 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.
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