Dada una string, encuentre su primer carácter que no se repite

Posted on by Rudeus Greyrat

Dada una string, encuentre el primer carácter que no se repite en ella. Por ejemplo, si la string de entrada es «GeeksforGeeks», la salida debería ser ‘f’ y si la string de entrada es «GeeksQuiz», la salida debería ser ‘G’. 

find-first-non-repeated-character-in-a-string

Ejemplo: 

Input: "geeksforgeeks"
Explanation:
Step 1: Construct a character count array 
        from the input string.
   ....
  count['e'] = 4
  count['f'] = 1
  count['g'] = 2
  count['k'] = 2
  ……

Step 2: Get the first character who's 
        count is 1 ('f').

Método n.º 1:   HashMap y recorridos de métodos de dos strings.

Se dice que un carácter no se repite si su frecuencia en la string es la unidad. Ahora, para encontrar tales caracteres, uno necesita encontrar la frecuencia de todos los caracteres en la string y verificar qué carácter tiene frecuencia unitaria . Esta tarea podría realizarse de manera eficiente utilizando un hash_map que asignará el personaje a sus respectivas frecuencias y en el que podemos actualizar simultáneamente la frecuencia de cualquier personaje con el que nos encontremos en un tiempo constante. Los caracteres distintos máximos en el sistema ASCII son 256 . Entonces hash_map tiene un tamaño máximo de 256 . Ahora lea la string nuevamente y el primer carácter que encontramos tiene una frecuencia como la unidad es la respuesta. 

Algoritmo: 

  1. Cree un hash_map que asignará el carácter a sus respectivas frecuencias.
  2. Recorre la string dada usando un puntero.
  3. Aumente la cantidad de caracteres actuales en hash_map .
  4. Ahora recorra la string nuevamente y verifique si el carácter actual tiene frecuencia = 1 .
  5. Si la frecuencia> 1 continúa el recorrido.
  6. De lo contrario, rompa el bucle e imprima el carácter actual como respuesta.

Pseudocódigo: 

for ( i=0 to str.length())
hash_map[str[i]]++;

for(i=0 to str.length())
  if(hash_map[str[i]]==1)
  return str[i]

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

C++

// C++ program to find first
// non-repeating character
#include <iostream>
using namespace std;
#define NO_OF_CHARS 256
 
/* Returns an array of size 256 containing count
of characters in the passed char array */
int* getCharCountArray(char* str)
{
    int* count = (int*)calloc(sizeof(int), NO_OF_CHARS);
    int i;
    for (i = 0; *(str + i); i++)
        count[*(str + i)]++;
    return count;
}
 
/* The function returns index of first
non-repeating character in a string. If all
characters are repeating then returns -1 */
int firstNonRepeating(char* str)
{
    int* count = getCharCountArray(str);
    int index = -1, i;
 
    for (i = 0; *(str + i); i++) {
        if (count[*(str + i)] == 1) {
            index = i;
            break;
        }
    }
 
    // To avoid memory leak
    free(count);
    return index;
}
 
/* Driver program to test above function */
int main()
{
    char str[] = "geeksforgeeks";
    int index = firstNonRepeating(str);
    if (index == -1)
        cout << "Either all characters are repeating or "
            "string is empty";
    else
        cout << "First non-repeating character is "<<
            str[index];
    getchar();
    return 0;
}
 
// This code is contributed by shivanisinghss2110

C

// C program to find first
// non-repeating character
#include <stdio.h>
#include <stdlib.h>
#define NO_OF_CHARS 256
 
/* Returns an array of size 256 containing count
   of characters in the passed char array */
int* getCharCountArray(char* str)
{
    int* count = (int*)calloc(sizeof(int), NO_OF_CHARS);
    int i;
    for (i = 0; *(str + i); i++)
        count[*(str + i)]++;
    return count;
}
 
/* The function returns index of first
   non-repeating character in a string. If all
   characters are repeating then returns -1 */
int firstNonRepeating(char* str)
{
    int* count = getCharCountArray(str);
    int index = -1, i;
 
    for (i = 0; *(str + i); i++) {
        if (count[*(str + i)] == 1) {
            index = i;
            break;
        }
    }
 
    // To avoid memory leak
    free(count);
    return index;
}
 
/* Driver program to test above function */
int main()
{
    char str[] = "geeksforgeeks";
    int index = firstNonRepeating(str);
    if (index == -1)
        printf("Either all characters are repeating or "
               "string is empty");
    else
        printf("First non-repeating character is %c",
               str[index]);
    getchar();
    return 0;
}

Java

// Java program to find first
// non-repeating character
class GFG {
    static final int NO_OF_CHARS = 256;
    static char count[] = new char[NO_OF_CHARS];
 
    /* calculate count of characters
       in the passed string */
    static void getCharCountArray(String str)
    {
        for (int i = 0; i < str.length(); i++)
            count[str.charAt(i)]++;
    }
 
    /* The method returns index of first non-repeating
       character in a string. If all characters are repeating
       then returns -1 */
    static int firstNonRepeating(String str)
    {
        getCharCountArray(str);
        int index = -1, i;
 
        for (i = 0; i < str.length(); i++) {
            if (count[str.charAt(i)] == 1) {
                index = i;
                break;
            }
        }
 
        return index;
    }
 
    // Driver method
    public static void main(String[] args)
    {
        String str = "geeksforgeeks";
        int index = firstNonRepeating(str);
 
        System.out.println(
            index == -1
                ? "Either all characters are repeating or string "
                      + "is empty"
                : "First non-repeating character is "
                      + str.charAt(index));
    }
}

Python3

# Python program to print the first non-repeating character
NO_OF_CHARS = 256
 
# Returns an array of size 256 containing count
# of characters in the passed char array
def getCharCountArray(string):
    count = [0] * NO_OF_CHARS
    for i in string:
        count[ord(i)]+= 1
    return count
 
# The function returns index of first non-repeating
# character in a string. If all characters are repeating
# then returns -1
def firstNonRepeating(string):
    count = getCharCountArray(string)
    index = -1
    k = 0
 
    for i in string:
        if count[ord(i)] == 1:
            index = k
            break
        k += 1
 
    return index
 
# Driver program to test above function
string = "geeksforgeeks"
index = firstNonRepeating(string)
if index == 1:
    print ("Either all characters are repeating or string is empty")
else:
    print ("First non-repeating character is" , string[index])
 
# This code is contributed by Bhavya Jain

C#

// C# program to find first non-repeating character
using System;
using System.Globalization;
 
class GFG {
 
    static int NO_OF_CHARS = 256;
    static char[] count = new char[NO_OF_CHARS];
 
    /* calculate count of characters
    in the passed string */
    static void getCharCountArray(string str)
    {
        for (int i = 0; i < str.Length; i++)
            count[str[i]]++;
    }
 
    /* The method returns index of first non-repeating
    character in a string. If all characters are
    repeating then returns -1 */
    static int firstNonRepeating(string str)
    {
        getCharCountArray(str);
        int index = -1, i;
 
        for (i = 0; i < str.Length; i++) {
            if (count[str[i]] == 1) {
                index = i;
                break;
            }
        }
 
        return index;
    }
 
    // Driver code
    public static void Main()
    {
        string str = "geeksforgeeks";
        int index = firstNonRepeating(str);
 
        Console.WriteLine(index == -1 ? "Either "
                                            + "all characters are repeating or string "
                                            + "is empty"
                                      : "First non-repeating character"
                                            + " is " + str[index]);
    }
}
 
// This code is contributed by Sam007

PHP

<?php
// PHP program to find
// first non-repeating
// character
$NO_OF_CHARS = 256;
$count=array_fill(0, 200, 0);
 
/* calculate count
   of characters in 
   the passed string */
function getCharCountArray($str)
{
    global $count;
    for ($i = 0;
         $i < strlen($str); $i++)
        $count[ord($str[$i])]++;
}
 
/* The method returns index
of first non-repeating
character in a string. If
all characters are repeating
then returns -1 */
function firstNonRepeating($str)
{
    global $count;
    getCharCountArray($str);
    $index = -1;
    for ($i = 0;
         $i < strlen($str); $i++)
    {
        if ($count[ord($str[$i])] == 1)
        {
            $index = $i;
            break;
        }
    }
     
return $index;
}
 
// Driver code
$str = "geeksforgeeks";
$index = firstNonRepeating($str);
if($index == -1)
echo "Either all characters are" .
     " repeating or string is empty";
else
echo "First non-repeating ".
            "character is ".
               $str[$index];
 
// This code is contributed by mits
?>
Producción

First non-repeating character is f

¿Se puede hacer esto atravesando la cuerda solo una vez?  
El enfoque anterior requiere tiempo O(n) , pero en la práctica se puede mejorar. La primera parte del algoritmo se ejecuta a través de la string para construir la array de conteo (en tiempo O(n) ). Esto es razonable. Pero la segunda parte sobre recorrer la string nuevamente solo para encontrar el primer no repetidor no es una buena práctica.
En situaciones reales, se espera que la string sea mucho más grande que su alfabeto. Tome las secuencias de ADN, por ejemplo, podrían tener millones de letras con un alfabeto de solo 4 letras. ¿Qué sucede si el no repetidor está al final de la string? Entonces tendríamos que escanear durante mucho tiempo (otra vez). 

Método #2: HashMap y recorrido de string única

Haga una array de conteo en lugar de hash_map de la cantidad máxima de caracteres (256). Podemos aumentar la array de conteo almacenando no solo conteos sino también el índice de la primera vez que encontró el carácter, por ejemplo (3, 26) para ‘a’, lo que significa que ‘a’ se contó 3 veces y la primera vez que se vio es en la posición 26. Entonces, cuando se trata de encontrar el primer no repetidor, solo tenemos que escanear la array de conteo, en lugar de la string. Gracias a Ben por sugerir este enfoque.

Algoritmo: 

  1. Cree un count_array que tendrá dos campos, a saber, frecuencia, primera aparición de un carácter .
  2. El tamaño de count_array es ‘256’ .
  3. Recorre la string dada usando un puntero.
  4. Aumente el recuento del carácter actual y actualice la ocurrencia.
  5. Ahora, aquí hay un problema, la array contendrá la primera aparición válida del carácter que tiene la unidad, de lo contrario, la primera aparición seguirá actualizándose.
  6. Ahora recorra el count_array y encuentre el carácter que tiene el valor mínimo de la primera aparición y el valor de frecuencia como unidad.
  7. Devuelve el personaje

Pseudocódigo: 

for ( i=0 to str.length())
count_arr[str[i]].first++;
count_arr[str[i]].second=i;

int res=INT_MAX;
for(i=0 to count_arr.size())
  if(count_arr[str[i]].first==1)
  res=min(min, count_arr[str[i]].second)

return res

Implementación:

C++

// CPP program to find first non-repeating
// character
#include <bits/stdc++.h>
using namespace std;
#define NO_OF_CHARS 256
 
/* The function returns index of the first
   non-repeating character in a string. If
   all characters are repeating then
   returns INT_MAX */
int firstNonRepeating(char* str)
{
    pair<int, int> arr[NO_OF_CHARS];
 
    for (int i = 0; str[i]; i++) {
        (arr[str[i]].first)++;
        arr[str[i]].second = i;
    }
 
    int res = INT_MAX;
    for (int i = 0; i < NO_OF_CHARS; i++)
 
        // If this character occurs only
        // once and appears before the
        // current result, then update the
        // result
        if (arr[i].first == 1)
            res = min(res, arr[i].second);
 
    return res;
}
 
/* Driver program to test above function */
int main()
{
    char str[] = "geeksforgeeks";
    int index = firstNonRepeating(str);
    if (index == INT_MAX)
        printf("Either all characters are "
               "repeating or string is empty");
    else
        printf("First non-repeating character"
               " is %c",
               str[index]);
    return 0;
}

C

#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#define NO_OF_CHARS 256
 
// Structure to store count of a
// character and index of the first
// occurrence in the input string
struct countIndex {
    int count;
    int index;
};
 
/* Returns an array of above
structure type. The size of
array is NO_OF_CHARS */
struct countIndex* getCharCountArray(char* str)
{
    struct countIndex* count = (struct countIndex*)calloc(
        sizeof(struct countIndex), NO_OF_CHARS);
    int i;
    for (i = 0; *(str + i); i++) {
        (count[*(str + i)].count)++;
 
        // If it's first occurrence,
        // then store the index
        if (count[*(str + i)].count == 1)
            count[*(str + i)].index = i;
    }
    return count;
}
 
/* The function returns index of the
    first non-repeating character in
    a string. If all characters are
    repeating then returns INT_MAX */
int firstNonRepeating(char* str)
{
    struct countIndex* count
        = getCharCountArray(str);
    int result = INT_MAX, i;
 
    for (i = 0; i < NO_OF_CHARS; i++) {
        // If this character occurs
        // only once and appears
        // before the current result,
        // then update the result
        if (count[i].count == 1
            && result > count[i].index)
            result = count[i].index;
    }
 
    // To avoid memory leak
    free(count);
    return result;
}
 
/* Driver program to test above function */
int main()
{
    char str[] = "geeksforgeeks";
    int index = firstNonRepeating(str);
    if (index == INT_MAX)
        printf("Either all characters are"
               " repeating or string is empty");
    else
        printf("First non-repeating character"
               " is %c",
               str[index]);
    getchar();
    return 0;
}

Java

// Java program to find first
// non-repeating character
// Note : hashmap is used
 
import java.util.*;
 
class CountIndex {
    int count, index;
 
    // constructor for first occurrence
    public CountIndex(int index)
    {
        this.count = 1;
        this.index = index;
    }
 
    // method for updating count
    public void incCount()
    {
        this.count++;
    }
}
class GFG {
    static final int NO_OF_CHARS = 256;
 
    static HashMap<Character, CountIndex> hm
        = new HashMap<Character, CountIndex>(NO_OF_CHARS);
 
    /* calculate count of characters
       in the passed string */
    static void getCharCountArray(String str)
    {
        for (int i = 0; i < str.length(); i++) {
            // If character already occurred,
            if (hm.containsKey(str.charAt(i))) {
                // updating count
                hm.get(str.charAt(i)).incCount();
            }
 
            // If it's first occurrence, then store
            // the index and count = 1
            else {
                hm.put(str.charAt(i), new CountIndex(i));
            }
        }
    }
 
    /* The method returns index of first non-repeating
       character in a string. If all characters are repeating
       then returns -1 */
    static int firstNonRepeating(String str)
    {
        getCharCountArray(str);
        int result = Integer.MAX_VALUE, i;
        for (Map.Entry<Character, CountIndex> entry : hm.entrySet())
        {
            int c=entry.getValue().count;
            int ind=entry.getValue().index;
            if(c==1 && ind < result)
            {
                result=ind;
            }
        }
       
 
        return result;
    }
 
    // Driver method
    public static void main(String[] args)
    {
        String str = "geeksforgeeks";
        int index = firstNonRepeating(str);
 
        System.out.println(
            index == Integer.MAX_VALUE
                ? "Either all characters are repeating "
                      + " or string is empty"
                : "First non-repeating character is "
                      + str.charAt(index));
    }
}

Python3

# Python3 program to find first non-repeating
# character
import sys
 
NO_OF_CHARS = 256
 
#    The function returns index of the first
#    non-repeating character in a string. If
#    all characters are repeating then
#    returns sys.maxsize :
def firstNonRepeating(Str):
 
    arr = [[] for i in range(NO_OF_CHARS)]
    for i in range(NO_OF_CHARS):
        arr[i] = [0,0]
 
    for i in range(len(Str)):
        arr[ord(Str[i])][0] += 1
        arr[ord(Str[i])][1]= i
 
 
    res = sys.maxsize
    for i in range(NO_OF_CHARS):
 
        # If this character occurs only
        # once and appears before the
        # current result, then update the
        # result
        if (arr[i][0] == 1):
            res = min(res, arr[i][1])
 
    return res
 
# Driver program to test above functionS
Str = "geeksforgeeks"
index = firstNonRepeating(Str)
if (index == sys.maxsize):
    print("Either all characters are repeating or string is empty")
else:
    print("First non-repeating character is ",Str[index])
     
# This code is contributed by shinjanpatra

C#

// C# program to find first
// non-repeating character
// Note : hashmap is used
using System;
using System.Collections.Generic;
 
class CountIndex {
    public int count, index;
 
    // constructor for first occurrence
    public CountIndex(int index)
    {
        this.count = 1;
        this.index = index;
    }
 
    // method for updating count
    public virtual void incCount()
    {
        this.count++;
    }
}
 
class GFG {
    public const int NO_OF_CHARS = 256;
 
    public static Dictionary<char,
                             CountIndex>
        hm = new Dictionary<char,
                            CountIndex>(NO_OF_CHARS);
 
    /* calculate count of characters
    in the passed string */
    public static void getCharCountArray(string str)
    {
        for (int i = 0; i < str.Length; i++) {
            // If character already occurred,
            if (hm.ContainsKey(str[i])) {
                // updating count
                hm[str[i]].incCount();
            }
 
            // If it's first occurrence, then
            // store the index and count = 1
            else {
                hm[str[i]] = new CountIndex(i);
            }
        }
    }
 
    /* The method returns index of first
    non-repeating character in a string.
    If all characters are repeating then
    returns -1 */
    internal static int firstNonRepeating(string str)
    {
        getCharCountArray(str);
        int result = int.MaxValue, i;
 
        for (i = 0; i < str.Length; i++) {
            // If this character occurs only
            // once and appears before the
            // current result, then update the result
            if (hm[str[i]].count == 1 && result > hm[str[i]].index) {
                result = hm[str[i]].index;
            }
        }
 
        return result;
    }
 
    // Driver Code
    public static void Main(string[] args)
    {
        string str = "geeksforgeeks";
        int index = firstNonRepeating(str);
 
        Console.WriteLine(
            index == int.MaxValue
                ? "Either all characters are repeating "
                      + " or string is empty"
                : "First non-repeating character is "
                      + str[index]);
    }
}
 
// This code is contributed by Shrikant13

Javascript

<script>
 
// JavaScript program to find first non-repeating
// character
 
const NO_OF_CHARS = 256
 
/* The function returns index of the first
   non-repeating character in a string. If
   all characters are repeating then
   returns Number.MAX_VALUE */
function firstNonRepeating(str)
{
    let arr = new Array(NO_OF_CHARS)
    for(let i=0;i<NO_OF_CHARS;i++){
        arr[i] = [0,0];
    }
 
    for (let i=0;i<str.length;i++) {
        arr[str.charCodeAt(i)][0]++;
        arr[str.charCodeAt(i)][1]= i;
    }
 
    let res = Number.MAX_VALUE;
    for (let i = 0; i < NO_OF_CHARS; i++)
 
        // If this character occurs only
        // once and appears before the
        // current result, then update the
        // result
        if (arr[i][0] == 1)
            res = Math.min(res, arr[i][1]);
 
    return res;
}
 
/* Driver program to test above function */
 
let str = "geeksforgeeks";
let index = firstNonRepeating(str);
if (index == Number.MAX_VALUE)
    document.write("Either all characters are repeating or string is empty");
else
    document.write("First non-repeating character is ",str[index]);
     
// code is contributed by shinjanpatra
 
</script>
Producción

First non-repeating character is f

Análisis de Complejidad: 

  • Complejidad temporal: O(n). 
    Como la string debe atravesarse al menos una vez.
  • Espacio Auxiliar: O(1). 
    El espacio está ocupado por el uso de count_array/hash_map para realizar un seguimiento de la frecuencia.

Método n.º 3: array de conteo y recorrido de una sola string:

Enfoque: haga una array de recuento del número máximo de caracteres (256). Podemos inicializar todos los elementos de esta array a -1. Y luego recorra nuestra string carácter por carácter y verifique si el elemento de la array con este carácter como índice es -1 o no. Si es -1, cámbielo a i y si no es -1, significa que este carácter ya apareció antes, así que cámbielo a -2. 

Al final, todos los caracteres repetidos se cambiarán a -2 y todos los caracteres que no se repitan contendrán el índice donde aparecen. Ahora podemos recorrer todos los caracteres que no se repiten y encontrar el índice mínimo o el primer índice.

Implementación:

C++

// CPP program to find first non-repeating
// character
# include<iostream>
# include<climits>
 
using namespace std;
 
// this function return the index of first non-repeating
// character if found, or else it returns -1
int firstNonRepeating(string str) {
    int fi[256]; // array to store First Index
 
    // initializing all elements to -1
    for(int i = 0; i<256; i++)
        fi[i] = -1;
 
    // sets all repeating characters to -2 and non-repeating characters
      // contain the index where they occur
    for(int i = 0; i<str.length(); i++) {
        if(fi[str[i]] == -1) {
            fi[str[i]] = i;
        }else {
            fi[str[i]] = -2;
        }
    }
 
    int res = INT_MAX;
 
    for(int i = 0; i<256; i++) {
 
        // If this character is not -1 or -2 then it
        // means that this character occurred only once
        // so find the min index of all characters that
        // occur only once, that's our first index
        if(fi[i] >= 0)
            res = min(res, fi[i]);
    }
     
    // if res remains INT_MAX, it means there are no
    // characters that repeat only once or the string is empty
    if(res == INT_MAX) return -1;
    else return res;
}
 
int main(){
    string str;
      str = "geeksforgeeks";
    int firstIndex = firstNonRepeating(str);
    if (firstIndex == -1)
        cout<<"Either all characters are repeating or string is empty";
    else
        cout<<"First non-repeating character is "<< str[firstIndex];
     
    return 0;
}

Java

// JAVA program to find first non-repeating
// character
public class GFG {
     
// this function return the index of first non-repeating
// character if found, or else it returns -1
public static int firstNonRepeating(String str) {
    int[] fi = new int [256]; // array to store First Index
 
    // initializing all elements to -1
    for(int i = 0; i<256; i++)
        fi[i] = -1;
 
    // sets all repeating characters to -2 and non-repeating characters
      // contain the index where they occur
    for(int i = 0; i<str.length(); i++) {
        if(fi[str.charAt(i)] == -1) {
            fi[str.charAt(i)] = i;
        }else {
            fi[str.charAt(i)] = -2;
        }
    }
 
    int res =  Integer.MAX_VALUE;
 
    for(int i = 0; i<256; i++) {
 
        // If this character is not -1 or -2 then it
        // means that this character occurred only once
        // so find the min index of all characters that
        // occur only once, that's our first index
        if(fi[i] >= 0)
            res = Math.min(res, fi[i]);
    }
     
    // if res remains  Integer.MAX_VALUE, it means there are no
    // characters that repeat only once or the string is empty
    if(res ==  Integer.MAX_VALUE) return -1;
    else return res;
}
 
public static void main(String args[]){
    String str;
    str = "geeksforgeeks";
    int firstIndex = firstNonRepeating(str);
    if (firstIndex == -1)
       System.out.println("Either all characters are repeating or string is empty");
    else
       System.out.println("First non-repeating character is "+ str.charAt(firstIndex));
    }
}
//This code is contributed by SoumikMondal

Python3

# this function return the index of first non-repeating
# character if found, or else it returns -1
import sys
 
def firstNonRepeating(Str):
    fi = [-1 for i in range(256)]
     
    # sets all repeating characters to -2 and non-repeating characters
    # contain the index where they occur
    for i in range(len(Str)):
     
        if(fi[ord(Str[i])] ==-1):
            fi[ord(Str[i])] = i
        else:
            fi[ord(Str[i])] = -2
         
    res = sys.maxsize
 
    for i in range(256):
 
        # If this character is not -1 or -2 then it
        # means that this character occurred only once
        # so find the min index of all characters that
        # occur only once, that's our first index
        if(fi[i] >= 0):
            res = min(res, fi[i])
     
    # if res remains INT_MAX, it means there are no
    # characters that repeat only once or the string is empty
    if(res == sys.maxsize):
        return -1
    else:
        return res
 
Str = "geeksforgeeks"
firstIndex = firstNonRepeating(Str)
 
if (firstIndex == -1):
    print("Either all characters are repeating or string is empty")
else:
    print("First non-repeating character is "+ str(Str[firstIndex]))
     
# This code is contributed by shinjanpatra

C#

// C# program to find first non-repeating
// character
using System;
public class GFG {
 
    // this function return the index of first non-repeating
    // character if found, or else it returns -1
    public static int firstNonRepeating(string str)
    {
        int[] fi
            = new int[256]; // array to store First Index
 
        // initializing all elements to -1
        for (int i = 0; i < 256; i++)
            fi[i] = -1;
 
        // sets all repeating characters to -2 and
        // non-repeating characters contain the index where
        // they occur
        for (int i = 0; i < str.Length; i++) {
            if (fi[str[i]] == -1) {
                fi[str[i]] = i;
            }
            else {
                fi[str[i]] = -2;
            }
        }
 
        int res = Int32.MaxValue;
 
        for (int i = 0; i < 256; i++) {
 
            // If this character is not -1 or -2 then it
            // means that this character occurred only once
            // so find the min index of all characters that
            // occur only once, that's our first index
            if (fi[i] >= 0)
                res = Math.Min(res, fi[i]);
        }
 
        // if res remains  Integer.MAX_VALUE, it means there
        // are no characters that repeat only once or the
        // string is empty
        if (res == Int32.MaxValue)
            return -1;
        else
            return res;
    }
 
    public static void Main()
    {
        string str;
        str = "geeksforgeeks";
        int firstIndex = firstNonRepeating(str);
        if (firstIndex == -1)
            Console.WriteLine(
                "Either all characters are repeating or string is empty");
        else
            Console.WriteLine(
                "First non-repeating character is "
                + str[firstIndex]);
    }
}
 
// This code is contributed by ukasp.

Javascript

<script>
 
// this function return the index of first non-repeating
// character if found, or else it returns -1
function firstNonRepeating(str)
{
    var fi=new Array(256);
     
    // array to store First Index
    fi.fill(-1);
 
    // initializing all elements to -1
    for(var i = 0; i<256; i++)
        fi[i] = -1;
 
    // sets all repeating characters to -2 and non-repeating characters
    // contain the index where they occur
    for(var i = 0; i<str.length; i++)
    {
        if(fi[str.charCodeAt(i)] ==-1)
        {
            fi[str.charCodeAt(i)] = i;
             
        }
        else
        {
            fi[str.charCodeAt(i)] = -2;
        }
    }
 
    var res = Infinity;
 
    for(var i = 0; i<256; i++) {
 
        // If this character is not -1 or -2 then it
        // means that this character occurred only once
        // so find the min index of all characters that
        // occur only once, that's our first index
        if(fi[i] >= 0)
            res = Math.min(res, fi[i]);
    }
     
    // if res remains INT_MAX, it means there are no
    // characters that repeat only once or the string is empty
    if(res == Infinity) return -1;
    else return res;
}
 
var str;
    str = "geeksforgeeks";
    var firstIndex = firstNonRepeating(str);
    if (firstIndex === -1)
        document.write("Either all characters are repeating or string is empty");
    else
        document.write("First non-repeating character is "+ str.charAt(firstIndex));
     
// This code is contributed by akshitsaxenaa09.   
</script>

Producción

First non-repeating character is f

Análisis de Complejidad:

  • Complejidad temporal : O(n).
    Como la string debe atravesarse una vez
  • Espacio Auxiliar: O(1).
    El espacio está ocupado por el uso de array de conteo para realizar un seguimiento de la frecuencia.

Método n.º 4: uso de funciones integradas de Python:

Acercarse:

  1. Calcule todas las frecuencias de todos los caracteres usando la función Counter() .
  2. Atraviese la cuerda y verifique si algún elemento tiene frecuencia 1.
  3. Imprime el carácter y rompe el ciclo.

A continuación se muestra la implementación:

Python3

# Python implementation
from collections import Counter
 
# Function which repeats
# first Nonrepeating character
def printNonrepeated(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 printNonrepeated function
printNonrepeated(string)
 
# this code is contributed by vikkycirus
Producción

f

Complejidad temporal: O(n). Como la string debe atravesarse al menos una vez.
Espacio Auxiliar: O(n). 

Usando la función de string find():

Enfoque: busque cada letra después de su posición actual. si devuelve -1, significa que la letra tiene solo una ocurrencia que es el índice actual.

Implementación:

C++

// C++ implementation
 
#include<bits/stdc++.h>
using namespace std;
 
void FirstNonRepeat(string s){
 
   for(int i = 0; i < s.length(); i++)
   {
 
       if (s.find(s[i] ,s.find(s[i])+1) == string::npos)
       {
           cout<<s[i];
 
           break;
       }
   }
   return;
}
 
// driver code
int main(){
        
    string s = "geeksforgeeks";
    FirstNonRepeat(s);
 
}
 
// This code is contributed by shinjanpatra

Python3

# python3 implementation
 
def FirstNonRepeat(s):
 
   for i in s:
 
       if (s.find(i,(s.find(i)+1))) == -1:
 
           print(i)
 
           break
 
   return
 
#__main__
 
s = 'geeksforgeeks'
 
FirstNonRepeat(s)

C#

// C# program to find first non-repeating
// character
using System;
 
public static class GFG
{
 
  // Function which repeats
  // first Nonrepeating character
  public static void FirstNonRepeat(string s)
  {
 
    for (int i = 0; i < s.Length; i++) {
 
      if (s.IndexOf(s[i], s.IndexOf(s[i]) + 1)
          == -1) {
        Console.Write(s[i]);
 
        break;
      }
    }
    return;
  }
 
  // driver code
  internal static void Main()
  {
 
    string s = "geeksforgeeks";
    FirstNonRepeat(s);
  }
}
 
// This code is contributed by Aarti_Rathi

Javascript

<script>
 
// JavaScript implementation
 
function FirstNonRepeat(s){
 
   for(let i = 0; i < s.length; i++)
   {
 
       if (s.indexOf(s.charAt(i),s.indexOf(s.charAt(i))+1) == -1)
       {
           document.write(s[i])
 
           break
       }
   }
   return
}
 
// driver code
let s = 'geeksforgeeks'
FirstNonRepeat(s)
 
// This code is contributed by shinjanpatra
 
</script>
Producción

f

Complejidad de Tiempo: O(n^2)
Espacio Auxiliar: O(1). 

 Enfoque: Usando el método count(). Si el recuento de un carácter en particular dentro de la string es 1, entonces el carácter no se repite. Después de encontrar el primer carácter que no se repite, rompa el bucle y muéstrelo.

Python3

# Python program to print the first non-repeating character
 
string = "geeksforgeeks"
index=-1
fnc=""
for i in string:
    if string.count(i) == 1:
        fnc+=i
        break
    else:
        index+=1
if index == 1:
  print ("Either all characters are repeating or string is empty")
else:
  print ("First non-repeating character is" , fnc)
Producción

First non-repeating character is f

Problema relacionado: K’th Carácter no repetitivo
Sugiera si alguien tiene una mejor solución que sea más eficiente en términos de espacio y tiempo.
Este artículo es una contribución de Aarti_Rathi . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *