Encuentra el carácter repetido presente primero en una string

Dada una string, encuentre el carácter repetido presente primero en la string.
(No es el primer carácter repetido, que se encuentra aquí ). 

Ejemplos: 

Input  : geeksforgeeks
Output : g
(mind that it will be g, not e.)

Preguntado en: pasantía Goldman Sachs 

Solución simple usando complejidad O(N^2): La solución es recorrer la string para cada carácter y buscar lo mismo en el resto de la string. Esto necesitaría dos bucles y, por lo tanto, no sería óptimo.  

Implementación:

// C++ program to find the first
// character that is repeated
#include <bits/stdc++.h>
#include <string.h>
 
using namespace std;
int findRepeatFirstN2(char* s)
{
    // this is O(N^2) method
    int p = -1, i, j;
    for (i = 0; i < strlen(s); i++)
    {
        for (j = i + 1; j < strlen(s); j++)
        {
            if (s[i] == s[j])
            {
                p = i;
                break;
            }
        }
        if (p != -1)
            break;
    }
 
    return p;
}
 
// Driver code
int main()
{
    char str[] = "geeksforgeeks";
    int pos = findRepeatFirstN2(str);
    if (pos == -1)
        cout << "Not found";
    else
        cout << str[pos];
    return 0;
}
 
// This code is contributed
// by Akanksha Rai

// C program to find the first character that
// is repeated
#include <stdio.h>
#include <string.h>
 
int findRepeatFirstN2(char* s)
{
    // this is O(N^2) method
    int p = -1, i, j;
    for (i = 0; i < strlen(s); i++) {
        for (j = i + 1; j < strlen(s); j++) {
            if (s[i] == s[j]) {
                p = i;
                break;
            }
        }
        if (p != -1)
            break;
    }
 
    return p;
}
 
// Driver code
int main()
{
    char str[] = "geeksforgeeks";
    int pos = findRepeatFirstN2(str);
    if (pos == -1)
        printf("Not found");
    else
        printf("%c", str[pos]);
    return 0;
}

// Java program to find the first character
// that is repeated
import java.io.*;
import java.util.*;
 
class GFG {
 
    static int findRepeatFirstN2(String s)
    {
         
        // this is O(N^2) method
        int p = -1, i, j;
        for (i = 0; i < s.length(); i++)
        {
            for (j = i + 1; j < s.length(); j++)
            {
                if (s.charAt(i) == s.charAt(j))
                {
                    p = i;
                    break;
                }
            }
            if (p != -1)
                break;
        }
     
        return p;
    }
     
    // Driver code
    static public void main (String[] args)
    {
        String str = "geeksforgeeks";
        int pos = findRepeatFirstN2(str);
         
        if (pos == -1)
            System.out.println("Not found");
        else
        System.out.println( str.charAt(pos));
    }
}
 
// This code is contributed by anuj_67.

# Python3 program to find the first
# character that is repeated
 
def findRepeatFirstN2(s):
 
    # this is O(N^2) method
    p = -1
    for i in range(len(s)):
     
        for j in range (i + 1, len(s)):
         
            if (s[i] == s[j]):
                p = i
                break
             
        if (p != -1):
            break
 
    return p
 
# Driver code
if __name__ == "__main__":
 
    str = "geeksforgeeks"
    pos = findRepeatFirstN2(str)
    if (pos == -1):
        print ("Not found")
    else:
        print (str[pos])
     
# This code is contributed
# by ChitraNayal

// C# program to find the first character
// that is repeated
using System;
 
class GFG {
 
    static int findRepeatFirstN2(string s)
    {
         
        // this is O(N^2) method
        int p = -1, i, j;
        for (i = 0; i < s.Length; i++)
        {
            for (j = i + 1; j < s.Length; j++)
            {
                if (s[i] == s[j])
                {
                    p = i;
                    break;
                }
            }
            if (p != -1)
                break;
        }
     
        return p;
    }
     
    // Driver code
    static public void Main ()
    {
        string str = "geeksforgeeks";
        int pos = findRepeatFirstN2(str);
         
        if (pos == -1)
            Console.WriteLine("Not found");
        else
        Console.WriteLine( str[pos]);
    }
}
 
// This code is contributed by anuj_67.

<?php
// PHP program to find the first
// character that is repeated
 
function findRepeatFirstN2($s)
{
    // this is O(N^2) method
    $p = -1;
    for ($i = 0; $i < strlen($s); $i++)
    {
        for ($j = ($i + 1);
             $j < strlen($s); $j++)
        {
            if ($s[$i] == $s[$j])
            {
                $p = $i;
                break;
            }
        }
        if ($p != -1)
            break;
    }
 
    return $p;
}
 
// Driver code
$str = "geeksforgeeks";
$pos = findRepeatFirstN2($str);
 
if ($pos == -1)
    echo ("Not found");
else
    echo ($str[$pos]);
 
// This code is contributed by jit_t
?>

<script>
 
// Javascript program to find the first
// character that is repeated
function findRepeatFirstN2(s)
{
     
    // This is O(N^2) method
    let p = -1, i, j;
    for(i = 0; i < s.length; i++)
    {
        for(j = i + 1; j < s.length; j++)
        {
            if (s[i] == s[j])
            {
                p = i;
                break;
            }
        }
        if (p != -1)
            break;
    }
    return p;
}
 
// Driver code
let str = "geeksforgeeks";
let pos = findRepeatFirstN2(str);
 
if (pos == -1)
    document.write("Not found");
else
    document.write(str[pos]);
     
// This code is contributed by suresh07  
 
</script>

g

Optimización por conteo de ocurrencias

Esta solución se optimiza mediante el uso de las siguientes técnicas: 

1. Recorremos la string y hacemos hash de los caracteres usando códigos ASCII. Almacene 1 si lo encuentra y almacene 2 si lo encuentra de nuevo. Además, almacene la posición de la primera letra encontrada en.
2. Ejecutamos un bucle en la array hash y ahora encontramos la posición mínima de cualquier carácter repetido.

Esto tendrá un tiempo de ejecución de O(N) .

Implementación:

// C++ program to find the first character that
// is repeated
#include<bits/stdc++.h>
 
using namespace std;
// 256 is taken just to ensure nothing is left,
// actual max ASCII limit is 128
#define MAX_CHAR 256
 
int findRepeatFirst(char* s)
{
    // this is optimized method
    int p = -1, i, k;
 
    // initialized counts of occurrences of
    // elements as zero
    int hash[MAX_CHAR] = { 0 };
 
    // initialized positions
    int pos[MAX_CHAR];
 
    for (i = 0; i < strlen(s); i++) {
        k = (int)s[i];
        if (hash[k] == 0) {
            hash[k]++;
            pos[k] = i;
        } else if (hash[k] == 1)
            hash[k]++;
    }
 
    for (i = 0; i < MAX_CHAR; i++) {
        if (hash[i] == 2) {
            if (p == -1) // base case
                p = pos[i];
            else if (p > pos[i])
                p = pos[i];
        }
    }
 
    return p;
}
 
// Driver code
int main()
{
    char str[] = "geeksforgeeks";
    int pos = findRepeatFirst(str);
    if (pos == -1)
        cout << "Not found";
    else
        cout << str[pos];
    return 0;
}
 
// This code is contributed
// by Akanksha Rai

// C program to find the first character that
// is repeated
#include <stdio.h>
#include <string.h>
 
// 256 is taken just to ensure nothing is left,
// actual max ASCII limit is 128
#define MAX_CHAR 256
 
int findRepeatFirst(char* s)
{
    // this is optimized method
    int p = -1, i, k;
 
    // initialized counts of occurrences of
    // elements as zero
    int hash[MAX_CHAR] = { 0 };
 
    // initialized positions
    int pos[MAX_CHAR];
 
    for (i = 0; i < strlen(s); i++) {
        k = (int)s[i];
        if (hash[k] == 0) {
            hash[k]++;
            pos[k] = i;
        } else if (hash[k] == 1)
            hash[k]++;
    }
 
    for (i = 0; i < MAX_CHAR; i++) {
        if (hash[i] == 2) {
            if (p == -1) // base case
                p = pos[i];
            else if (p > pos[i])
                p = pos[i];
        }
    }
 
    return p;
}
 
// Driver code
int main()
{
    char str[] = "geeksforgeeks";
    int pos = findRepeatFirst(str);
    if (pos == -1)
        printf("Not found");
    else
        printf("%c", str[pos]);
    return 0;
}

// Java Program to find the first character 
// that is repeated
 
import java.util.*;
import java.lang.*;
 
public class GFG
{
    public static int findRepeatFirst(String s)
    {
        // this is optimized method
        int p = -1, i, k;
 
        // initialized counts of occurrences of
        // elements as zero
        int MAX_CHAR = 256;
        int hash[] = new int[MAX_CHAR];
 
        // initialized positions
        int pos[] = new int[MAX_CHAR];
 
        for (i = 0; i < s.length(); i++)
        {
            k = (int)s.charAt(i);
            if (hash[k] == 0)
            {
                hash[k]++;
                pos[k] = i;
            }
            else if (hash[k] == 1)
                hash[k]++;
        }
 
        for (i = 0; i < MAX_CHAR; i++)
        {
            if (hash[i] == 2)
            {
                if (p == -1) // base case
                    p = pos[i];
                else if (p > pos[i])
                    p = pos[i];
            }
        }
 
        return p;
    }
 
// Driver code
    public static void main(String[] args)
    {
        String str = "geeksforgeeks";
        int pos = findRepeatFirst(str);
        if (pos == -1)
            System.out.println("Not found");
        else
            System.out.println(str.charAt(pos));
    }
}
 
// Code Contributed by Mohit Gupta_OMG

# Python 3 program to find the first
# character that is repeated
 
# 256 is taken just to ensure nothing
# is left, actual max ASCII limit is 128
 
MAX_CHAR = 256
 
def findRepeatFirst(s):
     
    # this is optimized method
    p = -1
 
    # initialized counts of occurrences
    # of elements as zero
    hash = [0 for i in range(MAX_CHAR)]
 
    # initialized positions
    pos = [0 for i in range(MAX_CHAR)]
 
    for i in range(len(s)):
        k = ord(s[i])
        if (hash[k] == 0):
            hash[k] += 1
            pos[k] = i
        elif(hash[k] == 1):
            hash[k] += 1
 
    for i in range(MAX_CHAR):
        if (hash[i] == 2):
            if (p == -1): # base case
                p = pos[i]
            elif(p > pos[i]):
                p = pos[i]
    return p
 
# Driver code
if __name__ == '__main__':
    str = "geeksforgeeks"
    pos = findRepeatFirst(str);
    if (pos == -1):
        print("Not found")
    else:
        print(str[pos])
         
# This code is contributed by
# Shashank_Sharma

// C# Program to find the first character 
// that is repeated
using System;
public class GFG
{
    public static int findRepeatFirst(string s)
    {
        // this is optimized method
        int p = -1, i, k;
  
        // initialized counts of occurrences of
        // elements as zero
        int MAX_CHAR = 256;
        int []hash = new int[MAX_CHAR];
  
        // initialized positions
        int []pos = new int[MAX_CHAR];
  
        for (i = 0; i < s.Length; i++)
        {
            k = (int)s[i];
            if (hash[k] == 0)
            {
                hash[k]++;
                pos[k] = i;
            }
            else if (hash[k] == 1)
                hash[k]++;
        }
  
        for (i = 0; i < MAX_CHAR; i++)
        {
            if (hash[i] == 2)
            {
                if (p == -1) // base case
                    p = pos[i];
                else if (p > pos[i])
                    p = pos[i];
            }
        }
  
        return p;
    }
  
    // Driver code
    public static void Main()
    {
        string str = "geeksforgeeks";
        int pos = findRepeatFirst(str);
        if (pos == -1)
            Console.Write("Not found");
        else
            Console.Write(str[pos]);
    }
}
  
// This code is contributed by nitin mittal.

<script>
    // Javascript Program to find the first character that is repeated
     
    function findRepeatFirst(s)
    {
        // this is optimized method
        let p = -1, i, k;
   
        // initialized counts of occurrences of
        // elements as zero
        let MAX_CHAR = 256;
        let hash = new Array(MAX_CHAR);
        hash.fill(0);
   
        // initialized positions
        let pos = new Array(MAX_CHAR);
        pos.fill(0);
   
        for (i = 0; i < s.length; i++)
        {
            k = s[i].charCodeAt();
            if (hash[k] == 0)
            {
                hash[k]++;
                pos[k] = i;
            }
            else if (hash[k] == 1)
                hash[k]++;
        }
   
        for (i = 0; i < MAX_CHAR; i++)
        {
            if (hash[i] == 2)
            {
                if (p == -1) // base case
                    p = pos[i];
                else if (p > pos[i])
                    p = pos[i];
            }
        }
   
        return p;
    }
     
    let str = "geeksforgeeks";
    let pos = findRepeatFirst(str);
    if (pos == -1)
      document.write("Not found");
    else
      document.write(str[pos]);
 
// This code is contributed by rameshtravel07.
</script>

g

Método n.º 3: Uso de las funciones integradas de Python:

Acercarse:

• Calcule todas las frecuencias de todos los caracteres usando la función Counter().
• Recorra la string y verifique si algún elemento tiene una frecuencia mayor que 1.
• Imprime el carácter y rompe el ciclo.

A continuación se muestra la implementación:

# Python implementation
from collections import Counter
 
# Function which repeats
# first repeating character
def printrepeated(string):
   
    # Calculating frequencies
    # using Counter function
    freq = Counter(string)
     
    # Traverse the string
    for i in string:
        if(freq[i] > 1):
            print(i)
            break
 
 
# Driver code
string = "geeksforgeeks"
 
# passing string to printrepeated function
printrepeated(string)
 
# this code is contributed by vikkycirus

g

Complejidad de tiempo:O(n)
Complejidad de espacio:O(n)

Método #4: Resolviendo solo por un solo recorrido de la string dada.

Algoritmo:

1. Atraviesa la cuerda de izquierda a derecha.
2. Si el carácter actual no está presente en el mapa hash, empuje este carácter junto con su índice.
3. Si el carácter actual ya está presente en el mapa hash, obtenga el índice del carácter actual (del mapa hash) y compárelo con el índice del carácter repetido encontrado anteriormente.
4. Si el índice actual es más pequeño, actualice el índice.

#include <iostream>
#include<unordered_map>
#define INT_MAX 2147483647
using namespace std;
 
// Function to find left most repeating character.
char firstRep (string s)
    {
        unordered_map<char,int> map;
        char c='#';
        int index=INT_MAX;
         
        // single traversal of string.
        for(int i=0;i<s.size();i++)
        {
            char p=s[i];
             
            if(map.find(p)==map.end())map.insert({p,i});
            else
            {
                if(map[p]<index)
                {
                    index=map[p];
                    c=p;
                }
            }
             
        }
         
         
        return c;
    }
 
// Main function.
int main() {
 
    // Input string.
    string s="abccdbd";
    cout<<firstRep(s)<<endl;
     
    return 0;
}
 
 
// This code is contributed
// by rohan007

// Java code to find the first repeating character in a
// string
import java.util.*;
 
public class GFG {
  public static int INT_MAX = 2147483647;
 
  // Function to find left most repeating character.
  public static char firstRep(String s)
  {
    HashMap<Character, Integer> map
      = new HashMap<Character, Integer>();
    char c = '#';
    int index = INT_MAX;
 
    // single traversal of string.
    for (int i = 0; i < s.length(); i++) {
      char p = s.charAt(i);
 
      if (!map.containsKey(p)) {
        map.put(p, i);
      }
      else {
        if (map.get(p) < index) {
          index = map.get(p);
          c = p;
        }
      }
    }
 
    return c;
  }
 
  // Main function.
  public static void main(String[] args)
  {
 
    // Input string.
    String s = "abccdbd";
    System.out.print(firstRep(s));
    System.out.print("\n");
  }
}
 
// This code is contributed by Aarti_Rathi

# Python3 code to find the first repeating character in a
# string
INT_MAX = 2147483647
 
# Function to find left most repeating character.
def firstRep(s):
    map = dict()
    c = '#'
    index = INT_MAX
     
    # single traversal of string.
    i = 0
    while (i < len(s)):
        p = s[i]
        if (not (p in map.keys())):
            map[p] = i
        else:
            if (map.get(p) < index):
                index = map.get(p)
                c = p
        i += 1
    return c
 
if __name__ == "__main__":
   
    # Input string.
    s = "abccdbd"
    print(firstRep(s), end="")
    print("\n", end="")
 
# This code is contributed by Aarti_Rathi

// C# code to find the first repeating character in a string
using System;
using System.Collections.Generic;
 
public static class GFG {
  static int INT_MAX = 2147483647;
 
  // Function to find left most repeating character.
  public static char firstRep(string s)
  {
    Dictionary<char, int> map
      = new Dictionary<char, int>();
    char c = '#';
    int index = INT_MAX;
 
    // single traversal of string.
    for (int i = 0; i < s.Length; i++) {
      char p = s[i];
 
      if (!map.ContainsKey(p)) {
        map[p] = i;
      }
      else {
        if (map[p] < index) {
          index = map[p];
          c = p;
        }
      }
    }
 
    return c;
  }
 
  // Main function.
  public static void Main()
  {
 
    // Input string.
    string s = "abccdbd";
    Console.Write(firstRep(s));
    Console.Write("\n");
  }
}
 
// This code is contributed by Aarti_Rathi

<script>
// JavaScript code to find the first repeating character in a string
const INT_MAX = 2147483647
 
// Function to find left most repeating character.
function firstRep(s)
{
    map = new Map();
    let c = '#';
    let index=INT_MAX;
         
    // single traversal of string.
    for(let i = 0; i < s.length; i++)
    {
        let p = s[i];
             
        if(!map.has(p))map.set(p,i);
        else
        {
            if(map.get(p) < index)
            {
                index = map.get(p);
                c = p;
            }
        }        
    }
    return c;
}
 
// Driver code
 
// Input string.
const s="abccdbd";
document.write(firstRep(s));
     
// This code is contributed by shinjanpatra
</script>

b

Complejidad temporal: O(N)
Complejidad espacial: O(N)

Solución más optimizada Carácter repetido cuya primera aparición está más a la izquierda

Este artículo es una contribución de Suprotik Dey . 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.