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 debe ser ‘f’ y si la string de entrada es «GeeksQuiz», la salida debe ser ‘G’.
Hemos discutido dos soluciones en Dada una string, encuentre su primer carácter que no se repite . En esta publicación, se analiza otra solución optimizada (sobre el método 2 de la publicación anterior ). La idea es optimizar el espacio. En lugar de usar un par para almacenar el recuento y el índice, usamos un solo elemento que almacena el índice si un elemento aparece una vez, de lo contrario almacena un valor negativo.
C++
// CPP program to find first non-repeating
// character using 1D array and one traversal.
#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)
{
// Initialize all characters as
// absent.
int arr[NO_OF_CHARS];
for (int i = 0; i < NO_OF_CHARS; i++)
arr[i] = -1;
// After below loop, the value of
// arr[x] is going to be index of
// of x if x appears only once. Else
// the value is going to be either
// -1 or -2.
for (int i = 0; str[i]; i++) {
if (arr[str[i]] == -1)
arr[str[i]] = i;
else
arr[str[i]] = -2;
}
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] >= 0)
res = min(res, arr[i]);
return res;
}
/* Driver program to test above function */
int main()
{
char str[] = "geeksforgeeks";
int index = firstNonRepeating(str);
if (index == INT_MAX)
cout <<"Either all characters are "
"repeating or string is empty";
else
cout <<"First non-repeating character"
" is "<< str[index];
return 0;
}
// This code is contributed by shivanisinghss210
C
// CPP program to find first non-repeating
// character using 1D array and one traversal.
#include <limits.h>
#include <stdio.h>
#include <math.h>
#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)
{
// Initialize all characters as
// absent.
int arr[NO_OF_CHARS];
for (int i = 0; i < NO_OF_CHARS; i++)
arr[i] = -1;
// After below loop, the value of
// arr[x] is going to be index of
// of x if x appears only once. Else
// the value is going to be either
// -1 or -2.
for (int i = 0; str[i]; i++) {
if (arr[str[i]] == -1)
arr[str[i]] = i;
else
arr[str[i]] = -2;
}
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] >= 0)
res = min(res, arr[i]);
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;
}
Java
// Java program to find first
// non-repeating character
// using 1D array and one
// traversal.
import java.io.*;
import java.util.*;
import java.lang.*;
class GFG
{
/* The function returns index
of the first non-repeating
character in a string. If
all characters are repeating
then returns INT_MAX */
static int firstNonRepeating(String str)
{
int NO_OF_CHARS = 256;
// Initialize all characters
// as absent.
int arr[] = new int[NO_OF_CHARS];
for (int i = 0;
i < NO_OF_CHARS; i++)
arr[i] = -1;
// After below loop, the
// value of arr[x] is going
// to be index of x if x
// appears only once. Else
// the value is going to be
// either -1 or -2.
for (int i = 0;
i < str.length(); i++)
{
if (arr[str.charAt(i)] == -1)
arr[str.charAt(i)] = i;
else
arr[str.charAt(i)] = -2;
}
int res = Integer.MAX_VALUE;
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] >= 0)
res = Math.min(res, arr[i]);
return res;
}
// Driver Code
public static void main(String args[])
{
String str = "geeksforgeeks";
int index = firstNonRepeating(str);
if (index == Integer.MAX_VALUE)
System.out.print("Either all characters are " +
"repeating or string is empty");
else
System.out.print("First non-repeating character"+
" is " + str.charAt(index));
}
}
Python3
'''
Python3 implementation to find non repeating character using
1D array and one traversal'''
import math as mt
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 '''
def firstNonRepeating(string):
#initialize all character as absent
arr=[-1 for i in range(NO_OF_CHARS)]
'''
After below loop, the value of
arr[x] is going to be index of
of x if x appears only once. Else
the value is going to be either
-1 or -2.'''
for i in range(len(string)):
if arr[ord(string[i])]==-1:
arr[ord(string[i])]=i
else:
arr[ord(string[i])]=-2
res=10**18
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:
res=min(res,arr[i])
return res
#Driver program to test above function
string="geeksforgeeks"
index=firstNonRepeating(string)
if index==10**18:
print("Either all characters are repeating or string is empty")
else:
print("First non-repeating character is",string[index])
#this code is contributed by Mohit Kumar 29
C#
// C# program to find first
// non-repeating character
// using 1D array and one
// traversal.
using System;
class GFG
{
/* The function returns index
of the first non-repeating
character in a string. If
all characters are repeating
then returns INT_MAX */
static int firstNonRepeating(String str)
{
int NO_OF_CHARS = 256;
// Initialize all characters
// as absent.
int []arr = new int[NO_OF_CHARS];
for (int i = 0; i < NO_OF_CHARS; i++)
arr[i] = -1;
// After below loop, the
// value of arr[x] is going
// to be index of x if x
// appears only once. Else
// the value is going to be
// either -1 or -2.
for (int i = 0; i < str.Length; i++)
{
if (arr[str[i]] == -1)
arr[str[i]] = i;
else
arr[str[i]] = -2;
}
int res = int.MaxValue;
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] >= 0)
res = Math.Min(res, arr[i]);
return res;
}
// Driver Code
public static void Main()
{
String str = "geeksforgeeks";
int index = firstNonRepeating(str);
if (index == int.MaxValue)
Console.Write("Either all characters are " +
"repeating or string is empty");
else
Console.Write("First non-repeating character"+
" is " + str[index]);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript program to find first
// non-repeating character
// using 1D array and one
// traversal.
/* The function returns index
of the first non-repeating
character in a string. If
all characters are repeating
then returns INT_MAX */
function firstNonRepeating(str)
{
let NO_OF_CHARS = 256;
// Initialize all characters
// as absent.
let arr = new Array(NO_OF_CHARS);
for (let i = 0;
i < NO_OF_CHARS; i++)
arr[i] = -1;
// After below loop, the
// value of arr[x] is going
// to be index of x if x
// appears only once. Else
// the value is going to be
// either -1 or -2.
for (let i = 0;
i < str.length; i++)
{
if (arr[str[i].charCodeAt(0)] == -1)
arr[str[i].charCodeAt(0)] = i;
else
arr[str[i].charCodeAt(0)] = -2;
}
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)
res = Math.min(res, arr[i]);
return res;
}
// Driver Code
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]);
// This code is contributed by patel2127
</script>
Producción
First non-repeating character is f
Complejidad de tiempo: O(n)
Implementación alternativa
Esto se codifica usando un HashMap o Técnica Hashing.
Si el elemento (o clave) se repite en la string, HashMap (o Diccionario) cambiará el valor de esa clave a Ninguno.
De esta manera, más adelante solo encontraremos claves cuyo valor sea «no Ninguno».
Python3
# Python implementation of
# above approach
from collections import Counter
def makeHashMap(string):
# Use Counter to make a frequency
# dictionary of characters in a string.
d1 = Counter(string)
# Update value of each key such that
# if frequency of frequency of a key
# is equal to 1, then it is set to 0,
# else set the value equal to None
d1 = {(key): (0 if d1[key] == 1 else None)
for key, value in d1.items()}
return d1
def firstNotRepeatingCharacter(s):
d = makeHashMap(s)
# variable to store the first
# non repeating character.
nonRep = None
# Traversing through the string only once.
for i in s:
if d[i] is not None:
'''
As soon as the first character in the string is
found whose value in the HashMap is "not None",
that is our first non-repeating character.
So we store it in nonRep and break out of the
loop. Thus saving on time.
'''
nonRep = i
break
if nonRep is not None:
return nonRep
else:
# If there are no non-repeating characters
# then "_" is returned
return str("_")
# Driver Code
print(firstNotRepeatingCharacter('bbcdcca'))
# This code is contributed by Vivek Nigam (@viveknigam300)
Producción
d
Complejidad de tiempo: O(N)
Método 3: a continuación se menciona otro enfoque simple para este problema sin usar ningún mapa hash o array. Podemos encontrar el primer carácter que no se repite simplemente usando un solo bucle for.
Otro enfoque:
Para contar la frecuencia de carácter podemos hacer el siguiente paso:
frecuencia de un carácter = longitud_de_la_string – longitud_de_la_string_sin_ese_carácter
por ejemplo: Give String es «hola» y queremos contar la frecuencia del carácter «h», por lo que al usar la fórmula anterior podemos decir
frecuencia del carácter “h” = 6 (longitud de la string) – 4 (longitud de la string sin “h”)
= 2
Entonces, de esta manera, podemos contar la frecuencia de cada carácter en una string y luego, si encontramos count == 1, eso significa que ese carácter es el primer carácter que no se repite en la string.
Implementación: La implementación del método anterior en Java se muestra a continuación:
Java
// Java program for the above approach
public class first_non_repeating {
static int firstNonRepeating(String str)
{
boolean flag = false;
int index = -1;
for (int i = 0; i < s.length(); i++) {
// Here I am replacing a character with "" and
// then finding the length after replacing and
// then subtracting length of that replaced
// string from the total length of the original
// string
int count_occurrence
= s.length()
- s.replace(
Character.toString(s.charAt(i)),
"")
.length();
if (count_occurrence == 1) {
flag = true;
index = i;
break;
}
}
if (flag)
System.out.println(
"First non repeating character is "
+ s.charAt(index));
else
System.out.println(
"There is no non-repeating character
is present in the string");
}
// Driver Code
public static void main(String arg[])
{
String s = "GeeksforGeeks";
firstNonRepeating(s);
}
}
// This Solution is contributed by Sourabh Sharma.
Python3
# Python implementation of above approach
def firstNonRepeating(s):
flag = False
index = -1
for i in range(len(s)):
# Here I am replacing a character with "" and
# then finding the length after replacing and
# then subtracting length of that replaced
# string from the total length of the original
# string
count_occurrence = len(s) - len(s.replace(s[i],''))
if (count_occurrence == 1):
flag = True
index = i
break
if (flag):
print(f"First non repeating character is {s[index]}")
else:
print("There is no non-repeating character is present in the string")
# Driver Code
s = "GeeksforGeeks"
firstNonRepeating(s)
# This code is contributed by shinjanpatra
Javascript
<script>
// JavaScript implementation of above approach
function firstNonRepeating(s)
{
let flag = false;
let index = -1;
for (let i = 0; i < s.length; i++) {
// Here I am replacing a character with "" and
// then finding the length after replacing and
// then subtracting length of that replaced
// string from the total length of the original
// string
let count_occurrence
= s.length - s.replaceAll(s[i],'').length;
if (count_occurrence == 1)
{
flag = true;
index = i;
break;
}
}
if (flag)
document.write(
"First non repeating character is "
+ s[index],"</br>");
else
document.write(
"There is no non-repeating character is present in the string","</br>");
}
// Driver Code
let s = "GeeksforGeeks"
firstNonRepeating(s)
// This code is contributed by shinjanpatra
</script>
Producción
First non repeating character is f
Complejidad de tiempo: O(N)
Espacio Auxiliar: O(1)