Implemente un algoritmo eficiente en el espacio para verificar el primer carácter repetido en una string sin usar ninguna estructura de datos adicional en un recorrido. No se permite el uso de estructuras de datos adicionales como array de conteo, hash, etc.
Ejemplos:
Input : abcfdeacf Output : char = a, index= 6
La idea es usar una variable entera y usa 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.
Implementación:
C++
// Efficiently check First repeated character
// in C++ program
#include<bits/stdc++.h>
using namespace std;
// Returns -1 if all characters of str are
// unique.
// Assumptions : (1) str contains only characters
// from 'a' to 'z'
// (2) integers are stored using 32
// bits
int FirstRepeated(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 i;
// set bit in checker
checker |= (1 << val);
}
return -1;
}
// Driver code
int main()
{
string s = "abcfdeacf";
int i=FirstRepeated(s);
if (i!=-1)
cout <<"Char = "<< s[i] << " and Index = "<<i;
else
cout << "No repeated Char";
return 0;
}
Java
// Efficiently check First repeated character
// in Java program
public class First_Repeated_char {
static int FirstRepeated(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 i;
// set bit in checker
checker |= (1 << val);
}
return -1;
}
// Driver code
public static void main(String args[])
{
String s = "abcfdeacf";
int i=FirstRepeated(s);
if (i!=-1)
System.out.println("Char = "+ s.charAt(i) + " and Index = "+i);
else
System.out.println( "No repeated Char");
}
}
// This code is contributed by Sumit Ghosh
Python3
# Efficiently check First repeated character
# in Python
# Returns -1 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 FirstRepeated(string):
# An integer to store presence/absence
# of 26 characters using its 32 bits.
checker = 0
pos = 0
for i in string:
val = ord(i) - ord('a');
# If bit corresponding to current
# character is already set
if ((checker & (1 << val)) > 0):
return pos
# set bit in checker
checker |= (1 << val)
pos += 1
return -1
# Driver code
string = "abcfdeacf"
i = FirstRepeated(string)
if i != -1:
print ("Char = ", string[i], " and Index = ", i)
else:
print ("No repeated Char")
# This code is contributed by Sachin Bisht
C#
// C# program to Efficiently
// check First repeated character
using System;
public class First_Repeated_char {
static int FirstRepeated(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 i;
// set bit in checker
checker |= (1 << val);
}
return -1;
}
// Driver code
public static void Main()
{
string s = "abcfdeacf";
int i=FirstRepeated(s);
if (i!=-1)
Console.WriteLine("Char = " + s[i] +
" and Index = " + i);
else
Console.WriteLine( "No repeated Char");
}
}
// This code is contributed by vt_m.
PHP
<?php
// Efficiently check First repeated character
// in PHP program
// Returns -1 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 FirstRepeated($str)
{
// An integer to store presence/absence
// of 26 characters using its 32 bits.
$checker = 0;
for ($i = 0; $i < strlen($str); ++$i)
{
$val = (ord($str[$i]) - ord('a'));
// If bit corresponding to current
// character is already set
if (($checker & (1 << $val)) > 0)
return $i;
// set bit in checker
$checker |= (1 << $val);
}
return -1;
}
// Driver code
$s = "abcfdeacf";
$i=FirstRepeated($s);
if ($i!=-1)
echo "Char = " . $s[$i] .
" and Index = " . $i;
else
echo "No repeated Char";
// This code is contributed by ita_c
?>
Javascript
<script>
// Efficiently check First repeated character
// in Javascript program
function FirstRepeated(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 i;
// set bit in checker
checker |= (1 << val);
}
return -1;
}
// Driver code
let s = "abcfdeacf";
let i=FirstRepeated(s);
if (i!=-1)
document.write("Char = "+ s[i] + " and Index = "+i);
else
document.write( "No repeated Char");
// This code is contributed by rag2127
</script>
Producción
Char = a and Index = 6
Complejidad temporal: O(n)
Espacio auxiliar: O(1)
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