Dada una string y un número k, encuentre el k-ésimo carácter no repetido en la string. Considere una string de entrada grande con lacs de caracteres y un juego de caracteres pequeño. ¿Cómo encontrar el carácter haciendo solo un recorrido de la string de entrada?
Ejemplos:
Input : str = geeksforgeeks, k = 3
Output : r
First non-repeating character is f,
second is o and third is r.
Input : str = geeksforgeeks, k = 2
Output : o
Input : str = geeksforgeeks, k = 4
Output : Less than k non-repeating
characters in input.
Este problema es principalmente una extensión del primer problema de caracteres no repetidos .
Método 1 (Simple: O(n 2 )
Una solución simple es ejecutar dos bucles. Comience a atravesar desde el lado izquierdo. Para cada carácter, verifique si se repite o no. Si el carácter no se repite, incremente el conteo de caracteres que no se repiten. caracteres. Cuando el recuento se convierte en k, devuelve el carácter.
Método 2 (O(n) pero requiere dos recorridos)
- Crea un hash vacío.
- Escanee la string de entrada de izquierda a derecha e inserte valores y sus recuentos en el hash.
- Escanee la string de entrada de izquierda a derecha y lleve el conteo de caracteres con conteos superiores a 1. Cuando el conteo se convierta en k, devuelva el carácter.
Método 3 (O(n) y requiere un recorrido)
La idea es utilizar dos arrays auxiliares de tamaño 256 (suponiendo que los caracteres se almacenan utilizando 8 bits). Las dos arrays son:
count[x] : Stores count of character 'x' in str.
If x is not present, then it stores 0.
index[x] : Stores indexes of non-repeating characters
in str. If a character 'x' is not present
or x is repeating, then it stores a value
that cannot be a valid index in str[]. For
example, length of string.
- Inicialice todos los valores en count[] como 0 y todos los valores en index[] como n donde n es la longitud de la string.
- Recorra la string de entrada str y haga lo siguiente para cada carácter c = str[i].
- Cuenta de incrementos[x].
- Si cuenta[x] es 1, entonces almacene el índice de x en índice[x], es decir, índice[x] = i
- Si count[x] es 2, entonces elimine x de index[], es decir, index[x] = n
- Ahora index[] tiene índices de todos los caracteres que no se repiten. Ordene index[] en orden creciente para que obtengamos el k-ésimo elemento más pequeño en index[k]. Tenga en cuenta que este paso toma tiempo O(1) porque solo hay 256 elementos en index[].
A continuación se muestra la implementación de la idea anterior.
C++
// C++ program to find k'th non-repeating character
// in a string
#include <bits/stdc++.h>
using namespace std;
const int MAX_CHAR = 256;
// Returns index of k'th non-repeating character in
// given string str[]
int kthNonRepeating(string str, int k)
{
int n = str.length();
// count[x] is going to store count of
// character 'x' in str. If x is not present,
// then it is going to store 0.
int count[MAX_CHAR];
// index[x] is going to store index of character
// 'x' in str. If x is not present or x is
// repeating, then it is going to store a value
// (for example, length of string) that cannot be
// a valid index in str[]
int index[MAX_CHAR];
// Initialize counts of all characters and indexes
// of non-repeating characters.
for (int i = 0; i < MAX_CHAR; i++)
{
count[i] = 0;
index[i] = n; // A value more than any index
// in str[]
}
// Traverse the input string
for (int i = 0; i < n; i++)
{
// Find current character and increment its
// count
char x = str[i];
++count[x];
// If this is first occurrence, then set value
// in index as index of it.
if (count[x] == 1)
index[x] = i;
// If character repeats, then remove it from
// index[]
if (count[x] == 2)
index[x] = n;
}
// Sort index[] in increasing order. This step
// takes O(1) time as size of index is 256 only
sort(index, index+MAX_CHAR);
// After sorting, if index[k-1] is value, then
// return it, else return -1.
return (index[k-1] != n)? index[k-1] : -1;
}
// Driver code
int main()
{
string str = "geeksforgeeks";
int k = 3;
int res = kthNonRepeating(str, k);
(res == -1)? cout << "There are less than k non-"
"repeating characters"
: cout << "k'th non-repeating character"
" is "<< str[res];
return 0;
}
Java
// Java program to find k'th non-repeating character
// in a string
import java.util.Arrays;
class GFG
{
public static int MAX_CHAR = 256;
// Returns index of k'th non-repeating character in
// given string str[]
static int kthNonRepeating(String str, int k)
{
int n = str.length();
// count[x] is going to store count of
// character 'x' in str. If x is not present,
// then it is going to store 0.
int[] count = new int[MAX_CHAR];
// index[x] is going to store index of character
// 'x' in str. If x is not present or x is
// repeating, then it is going to store a value
// (for example, length of string) that cannot be
// a valid index in str[]
int[] index = new int[MAX_CHAR];
// Initialize counts of all characters and indexes
// of non-repeating characters.
for (int i = 0; i < MAX_CHAR; i++)
{
count[i] = 0;
index[i] = n; // A value more than any index
// in str[]
}
// Traverse the input string
for (int i = 0; i < n; i++)
{
// Find current character and increment its
// count
char x = str.charAt(i);
++count[x];
// If this is first occurrence, then set value
// in index as index of it.
if (count[x] == 1)
index[x] = i;
// If character repeats, then remove it from
// index[]
if (count[x] == 2)
index[x] = n;
}
// Sort index[] in increasing order. This step
// takes O(1) time as size of index is 256 only
Arrays.sort(index);
// After sorting, if index[k-1] is value, then
// return it, else return -1.
return (index[k-1] != n)? index[k-1] : -1;
}
// driver program
public static void main (String[] args)
{
String str = "geeksforgeeks";
int k = 3;
int res = kthNonRepeating(str, k);
System.out.println(res == -1 ? "There are less than k non-repeating characters" :
"k'th non-repeating character is " + str.charAt(res));
}
}
// Contributed by Pramod Kumar
Python 3
# Python 3 program to find k'th
# non-repeating character in a string
MAX_CHAR = 256
# Returns index of k'th non-repeating
# character in given string str[]
def kthNonRepeating(str, k):
n = len(str)
# count[x] is going to store count of
# character 'x' in str. If x is not
# present, then it is going to store 0.
count = [0] * MAX_CHAR
# index[x] is going to store index of
# character 'x' in str. If x is not
# present or x is repeating, then it
# is going to store a value (for example,
# length of string) that cannot be a valid
# index in str[]
index = [0] * MAX_CHAR
# Initialize counts of all characters
# and indexes of non-repeating characters.
for i in range( MAX_CHAR):
count[i] = 0
index[i] = n # A value more than any
# index in str[]
# Traverse the input string
for i in range(n):
# Find current character and
# increment its count
x = str[i]
count[ord(x)] += 1
# If this is first occurrence, then
# set value in index as index of it.
if (count[ord(x)] == 1):
index[ord(x)] = i
# If character repeats, then remove
# it from index[]
if (count[ord(x)] == 2):
index[ord(x)] = n
# Sort index[] in increasing order. This step
# takes O(1) time as size of index is 256 only
index.sort()
# After sorting, if index[k-1] is value,
# then return it, else return -1.
return index[k - 1] if (index[k - 1] != n) else -1
# Driver code
if __name__ == "__main__":
str = "geeksforgeeks"
k = 3
res = kthNonRepeating(str, k)
if(res == -1):
print("There are less than k",
"non-repeating characters")
else:
print("k'th non-repeating character is",
str[res])
# This code is contributed
# by ChitraNayal
C#
// C# program to find k'th non-repeating
// character in a string
using System;
class GFG {
public static int MAX_CHAR = 256;
// Returns index of k'th non-repeating
// character in given string str[]
static int kthNonRepeating(String str, int k)
{
int n = str.Length;
// count[x] is going to store count of
// character 'x' in str. If x is not
// present, then it is going to store 0.
int []count = new int[MAX_CHAR];
// index[x] is going to store index of
// character 'x' in str. If x is not
// present or x is repeating, then it
// is going to store a value (for
// example, length of string) that
// cannot be a valid index in str[]
int []index = new int[MAX_CHAR];
// Initialize counts of all characters
// and indexes of non-repeating
// characters.
for (int i = 0; i < MAX_CHAR; i++)
{
count[i] = 0;
// A value more than any index
// in str[]
index[i] = n;
}
// Traverse the input string
for (int i = 0; i < n; i++)
{
// Find current character and
// increment its count
char x = str[i];
++count[x];
// If this is first occurrence,
// then set value in index as
// index of it.
if (count[x] == 1)
index[x] = i;
// If character repeats, then
// remove it from index[]
if (count[x] == 2)
index[x] = n;
}
// Sort index[] in increasing order.
// This step takes O(1) time as size
// of index is 256 only
Array.Sort(index);
// After sorting, if index[k-1] is
// value, then return it, else
// return -1.
return (index[k-1] != n) ?
index[k-1] : -1;
}
// driver program
public static void Main ()
{
String str = "geeksforgeeks";
int k = 3;
int res = kthNonRepeating(str, k);
Console.Write(res == -1 ? "There are less"
+ " than k non-repeating characters" :
"k'th non-repeating character is "
+ str[res]);
}
}
// This code is contributed by nitin mittal.
Javascript
<script>
// Javascript program to find k'th non-repeating character
// in a string
let MAX_CHAR = 256;
// Returns index of k'th non-repeating character in
// given string str[]
function kthNonRepeating(str,k)
{
let n = str.length;
// count[x] is going to store count of
// character 'x' in str. If x is not present,
// then it is going to store 0.
let count = new Array(MAX_CHAR);
// index[x] is going to store index of character
// 'x' in str. If x is not present or x is
// repeating, then it is going to store a value
// (for example, length of string) that cannot be
// a valid index in str[]
let index = new Array(MAX_CHAR);
// Initialize counts of all characters and indexes
// of non-repeating characters.
for (let i = 0; i < MAX_CHAR; i++)
{
count[i] = 0;
index[i] = n; // A value more than any index
// in str[]
}
// Traverse the input string
for (let i = 0; i < n; i++)
{
// Find current character and increment its
// count
let x = str[i];
++count[x.charCodeAt(0)];
// If this is first occurrence, then set value
// in index as index of it.
if (count[x.charCodeAt(0)] == 1)
index[x.charCodeAt(0)] = i;
// If character repeats, then remove it from
// index[]
if (count[x.charCodeAt(0)] == 2)
index[x.charCodeAt(0)] = n;
}
// Sort index[] in increasing order. This step
// takes O(1) time as size of index is 256 only
(index).sort(function(a,b){return a-b;});
// After sorting, if index[k-1] is value, then
// return it, else return -1.
return (index[k-1] != n)? index[k-1] : -1;
}
// driver program
let str = "geeksforgeeks";
let k = 3;
let res = kthNonRepeating(str, k);
document.write(res == -1 ? "There are less than k non-repeating characters" :
"k'th non-repeating character is " + str[res]);
// This code is contributed by ab2127
</script>
Producción:
k'th non-repeating character is r
Complejidad de tiempo: O(m log m), aquí m es MAX_CHARS = 256
Espacio auxiliar: O(m), aquí m es MAX_CHARS = 256
Solución optimizada para el espacio:
esto se puede optimizar para el espacio y se puede resolver utilizando solo una array de índice único. A continuación se muestra la solución optimizada para el espacio:
C++
#include <bits/stdc++.h>
using namespace std;
#define MAX_CHAR 256
int kthNonRepeating(string input, int k)
{
int inputLength = input.length();
/*
* indexArr will store index of non-repeating
* characters, inputLength for characters not in input
* and inputLength+1 for repeated characters.
*/
int indexArr[MAX_CHAR];
// initialize all values in indexArr as inputLength.
for (int i = 0; i < MAX_CHAR; i++) {
indexArr[i] = inputLength;
}
for (int i = 0; i < inputLength; i++) {
char c = input[i];
if (indexArr == inputLength) {
indexArr = i;
}
else {
indexArr = inputLength + 2;
}
}
sort(indexArr, indexArr + MAX_CHAR);
return (indexArr[k - 1] != inputLength)
? indexArr[k - 1]
: -1;
}
int main()
{
string input = "geeksforgeeks";
int k = 3;
int res = kthNonRepeating(input, k);
if (res == -1)
cout << "There are less than k non-repeating "
"characters";
else
cout << "k'th non-repeating character is "
<< input[res];
return 0;
}
// This code is contributed by gauravrajput1
Java
import java.util.*;
public class GFG {
public static int MAX_CHAR = 256;
public static void main (String[] args)
{
final String input = "geeksforgeeks";
int k = 3;
int res = kthNonRepeating(input, k);
System.out.println(res == -1 ? "There are less than k non-repeating characters" :
"k'th non-repeating character is " + input.charAt(res));
}
public static int kthNonRepeating(final String input, final int k) {
final int inputLength = input.length();
/*
* indexArr will store index of non-repeating characters,
* inputLength for characters not in input and
* inputLength+1 for repeated characters.
*/
final int[] indexArr = new int[MAX_CHAR];
// initialize all values in indexArr as inputLength.
Arrays.fill(indexArr, inputLength);
for (int i = 0; i < inputLength ; i++) {
final char c = input.charAt(i);
if (indexArr == inputLength) {
indexArr = i;
} else {
indexArr = inputLength + 2;
}
}
Arrays.sort(indexArr);
return (indexArr[k-1] != inputLength) ? indexArr[k-1] : -1;
}
}
// Contributed by AK
Python3
MAX_CHAR = 256
def kthNonRepeating(Input,k):
inputLength = len(Input)
# indexArr will store index of non-repeating characters,
# inputLength for characters not in input and
# inputLength+1 for repeated characters.
# initialize all values in indexArr as inputLength.
indexArr = [inputLength for i in range(MAX_CHAR)]
for i in range(inputLength):
c = Input[i]
if (indexArr[ord(c)] == inputLength):
indexArr[ord(c)] = i
else:
indexArr[ord(c)] = inputLength + 2
indexArr.sort()
if(indexArr[k - 1] != inputLength):
return indexArr[k - 1]
else:
return -1
Input = "geeksforgeeks"
k = 3
res = kthNonRepeating(Input, k)
if(res == -1):
print("There are less than k non-repeating characters")
else:
print("k'th non-repeating character is", Input[res])
# This code is contributed by rag2127
C#
using System;
public class GFG
{
public static int MAX_CHAR = 256;
static public void Main ()
{
string input = "geeksforgeeks";
int k = 3;
int res = kthNonRepeating(input, k);
Console.WriteLine(res == -1 ? "There are less than k non-repeating characters" :
"k'th non-repeating character is " + input[res]);
}
public static int kthNonRepeating(string input, int k) {
int inputLength = input.Length;
/*
* indexArr will store index of non-repeating characters,
* inputLength for characters not in input and
* inputLength+1 for repeated characters.
*/
int[] indexArr = new int[MAX_CHAR];
// initialize all values in indexArr as inputLength.
Array.Fill(indexArr, inputLength);
for (int i = 0; i < inputLength ; i++) {
char c = input[i];
if (indexArr == inputLength) {
indexArr = i;
} else {
indexArr = inputLength + 2;
}
}
Array.Sort(indexArr);
return (indexArr[k - 1] != inputLength) ? indexArr[k - 1] : -1;
}
}
// This code is contributed by avanitrachhadiya2155
Javascript
<script>
let MAX_CHAR = 256;
function kthNonRepeating(input, k)
{
let inputLength = input.length;
/*
* indexArr will store index of non-repeating characters,
* inputLength for characters not in input and
* inputLength+1 for repeated characters.
*/
let indexArr = new Array(MAX_CHAR);
// initialize all values in indexArr as inputLength.
for(let i=0;i<MAX_CHAR;i++)
{
indexArr[i]=inputLength;
}
for (let i = 0; i < inputLength ; i++) {
let c = input[i];
if (indexArr == inputLength) {
indexArr = i;
} else {
indexArr = inputLength + 2;
}
}
(indexArr).sort(function(a,b){return a-b;});
return (indexArr[k-1] != inputLength) ? indexArr[k-1] : -1;
}
let input = "geeksforgeeks";
let k = 3;
let res = kthNonRepeating(input, k);
document.write(res == -1 ? "There are less than k non-repeating characters" :
"k'th non-repeating character is " + input[res]);
// This code is contributed by unknown2108
</script>
Producción:
k'th non-repeating character is r
Complejidad de tiempo: O(m log m), aquí m es MAX_CHARS = 256
Espacio auxiliar: O(m), aquí m es MAX_CHARS = 256
Este artículo es una contribución de Aarti_Rathi y Shivam Gupta. Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo 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.
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