Encuentra el primer carácter repetido en una string

Dada una string, encuentra el primer carácter repetido en ella. Necesitamos encontrar el carácter que aparece más de una vez y cuyo índice de segunda aparición es el más pequeño. Una variación de esta pregunta se discute aquí .
 

Ejemplos: 

Entrada : ch = “geeksforgeeks” 
Salida : e 
e es el primer elemento que se repite

Entrada : str = “hola geeks” 
Salida : l 
l es el primer elemento que se repite

Solución simple : la solución es ejecutar dos bucles anidados. Comience a atravesar desde el lado izquierdo. Para cada carácter, compruebe si se repite o no. Si el carácter se repite, incremente el número de caracteres repetidos. Cuando la cuenta se convierte en K, devuelve el carácter. 
La complejidad temporal de esta solución es O(n ² )

Podemos usar la clasificación para resolver el problema en tiempo O (n Log n). Los siguientes son pasos detallados.  

• Copie la array dada en una array auxiliar temp[].
• Ordene la array temporal usando un algoritmo de clasificación de tiempo O (N log N).
• Escanee la array de entrada de izquierda a derecha. Para cada elemento, cuente sus ocurrencias en temp[] usando la búsqueda binaria. Tan pronto como encontramos un carácter que aparece más de una vez, lo devolvemos.

Este paso se puede realizar en tiempo O(N Log N).

Una solución eficiente es usar Hashing para resolver esto en tiempo O(N) en promedio. 

• Crea un hash vacío.
• Escanee cada carácter de la string de entrada e inserte valores para cada clave en el hash.
• Cuando cualquier carácter aparece más de una vez, el valor de la clave hash se incrementa en 1 y devuelve el carácter.

La imagen de abajo es una ejecución en seco del enfoque anterior:

A continuación se muestra la implementación del enfoque anterior:

// CPP program to find the first
// repeated character in a string
#include <bits/stdc++.h>
using namespace std;
 
// Returns first repeating character in str.
char firstRepeating(string &str)
{
    // Creates an empty hashset
    unordered_set<char> h;
 
    // Traverse the input array from left to right
    for (int i=0; i<str.length(); i++)
    {
        char c = str[i];
 
        // If element is already in hash set, update x
        // and then break
        if (h.find(c) != h.end())
            return c;
 
        else // Else add element to hash set
            h.insert(c);
    }
 
    // If there was no repeated character
    return '\0';
}
 
// Driver method to test above method
int main ()
{
    string str = "geeksforgeeks";
    cout << firstRepeating(str);
    return 0;
}

// Java program to find the first
// repeated character in a string
import java.util.*;
 
class Main
{
    // This function prints the first repeated
    // character in str[]
    static char firstRepeating(char str[])
    {
        // Creates an empty hashset
        HashSet<Character> h = new HashSet<>();
 
        // Traverse the input array from left to right
        for (int i=0; i<=str.length-1; i++)
        {
            char c = str[i];
 
            // If element is already in hash set, update x
            // and then break
            if (h.contains(c))
                return c;
 
            else // Else add element to hash set
                h.add(c);
        }
 
        return '\0';
    }
 
    // Driver method to test above method
    public static void main (String[] args)
    {
        String str = "geeksforgeeks";
        char[] arr = str.toCharArray();
        System.out.println(firstRepeating(arr));
    }
}

# Python program to find the first
# repeated character in a string
def firstRepeatedChar(str):
 
    h = {} # Create empty hash
 
    # Traverse each characters in string
    # in lower case order
    for ch in str:
 
        # If character is already present
        # in hash, return char
        if ch in h:
            return ch;
 
        # Add ch to hash
        else:
            h[ch] = 0
 
    return ''
 
 
# Driver code
print(firstRepeatedChar("geeksforgeeks"))

// C# program to find the first
// repeated character in a string
using System;
using System.Collections.Generic;
 
class GFG
{
// This function prints the first
// repeated character in str[]
public static char firstRepeating(char[] str)
{
    // Creates an empty hashset
    HashSet<char> h = new HashSet<char>();
 
    // Traverse the input array
    // from left to right
    for (int i = 0; i <= str.Length - 1; i++)
    {
        char c = str[i];
 
        // If element is already in hash set,
        // update x and then break
        if (h.Contains(c))
        {
            return c;
        }
 
        else // Else add element to hash set
        {
            h.Add(c);
        }
    }
 
    return '\0';
}
 
// Driver Code
public static void Main(string[] args)
{
    string str = "geeksforgeeks";
    char[] arr = str.ToCharArray();
    Console.WriteLine(firstRepeating(arr));
}
}
 
// This code is contributed by Shrikant13

<?php
// PHP program to find the first repeated
// character in a string
 
// Returns first repeating character in str.
function firstRepeating($str)
{
    // Creates an empty hashset
    $h = array();
 
    // Traverse the input array
    // from left to right
    for ($i = 0; $i < strlen($str); $i++)
    {
        $c = $str[$i];
 
        // If element is already in hash
        // set, update x and then break
        if (array_search($c, $h))
            return $c;
 
        else // Else add element to hash set
            array_push($h, $c);
    }
 
    // If there was no repeated character
    return '\0';
}
 
// Driver Code
$str = "geeksforgeeks";
echo firstRepeating($str);
 
// This code is contributed by ita_c
?>

<script>
 
// Javascript program to find the first
// repeated character in a string
     
// This function prints the first repeated
// character in str[]
function firstRepeating(str)
{
     
    // Creates an empty hashset
    let h = new Set();
     
    // Traverse the input array from left to right
    for(let i = 0; i <= str.length - 1; i++)
    {
        let c = str[i];
 
        // If element is already in hash
        // set, update x and then break
        if (h.has(c))
            return c;
             
        // Else add element to hash set
        else
            h.add(c);
    }
    return '\0';
}
 
// Driver code
let str = "geeksforgeeks";
document.write(firstRepeating(str));
 
// This code is contributed by avanitrachhadiya2155
 
</script>

Producción: 

e

Complejidad temporal : O(n) 
Espacio auxiliar : O(n)

Problema similar: encontrar el primer carácter no repetido en una string .

Este artículo es una contribución de Afzal Ansari . 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.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.