Dada una string str de tamaño N que contiene todos los caracteres posibles, incluidos los números enteros. Imprime Kth carácter distinto desde el comienzo de la string dada. Si K es más que el número de caracteres distintos, imprima -1 .
Nota:Las letras mayúsculas y minúsculas se consideran diferentes.
Ejemplos:
Entrada: str = “prophet1999”, K = 4
Salida: h
Explicación: El primer carácter distinto es ‘p’.
El segundo carácter distinto es ‘r’.
El tercer carácter distinto es ‘o’.
El cuarto carácter distinto es ‘h’.
‘p’ no es el cuarto carácter porque ya está presente antes de este punto y no es distinto.Entrada: str = “GeeksForGeeks”, K = 2
Salida: e
Explicación: El primer carácter distintivo es ‘G’.
El segundo carácter distinto es ‘e’.
Enfoque ingenuo: una solución simple es utilizar dos bucles anidados en los que el bucle exterior elige los caracteres de izquierda a derecha y el bucle interior comprueba si el carácter seleccionado está presente en otro lugar y lo convierte en el carácter nulo ‘\0’. Si el i-ésimo elemento no es ‘\0’, entonces incremente el conteo de elementos distintos . Si el recuento de elementos distintos se convierte en K , devuelve el elemento actual.
A continuación se muestra la implementación del enfoque anterior.
C++14
// C++ program to implement above approach
#include <bits/stdc++.h>
using namespace std;
// Function to print the Kth distinct character
int printKDistinct(string& str, int& K)
{
int distinct = 0, i, j, N = str.length();
if (K <= 0)
return -1;
for (i = 0; i < N; i++) {
for (j = i + 1; j < N; j++) {
if (str[i] == str[j])
str[j] = '\0';
}
if (str[i] != '\0')
distinct++;
if (distinct == K)
return str[i];
}
return -1;
}
// Driver code
int main()
{
string str = "GeeksForGeeks";
int K = 2;
int ans = printKDistinct(str, K);
if (ans == -1)
cout << -1;
else
cout << (char)ans;
return 0;
}
Java
// Java code to implement the approach
import java.io.*;
import java.util.*;
class GFG {
// Function to print the Kth distinct character
static int printKDistinct(char[] str, int K)
{
int distinct = 0, i, j, N = str.length;
if (K <= 0)
return -1;
for (i = 0; i < N; i++) {
for (j = i + 1; j < N; j++) {
if (str[i] == str[j])
str[j] = '\0';
}
if (str[i] != '\0')
distinct++;
if (distinct == K)
return str[i];
}
return -1;
}
// Driver code
public static void main(String[] args)
{
String str = "GeeksForGeeks";
int K = 2;
int ans = printKDistinct(str.toCharArray(), K);
if (ans == -1)
System.out.println(-1);
else
System.out.println((char)ans);
}
}
// This code is contributed by Karandeep1234
Python3
# Python program to implement above approach # Function to print the Kth distinct character def printKDistinct(Str, K): distinct,N = 0 ,len(Str) if (K <= 0): return -1 for i in range(N): for j in range(i + 1,N): if (Str[i] == Str[j]): Str.replace(Str[j],'\0') if (Str[i] != '\0'): distinct += 1 if (distinct == K): return Str[i] return -1 # Driver code Str = "GeeksForGeeks" K = 2 ans = printKDistinct(Str, K) if (ans == -1): print(-1) else: print(ans) # This code is contributed by shinjanpatra
C#
// C# code to implement the approach
using System;
public class GFG
{
// Function to print the Kth distinct character
static int printKDistinct(char[] str, int K)
{
int distinct = 0, i, j, N = str.Length;
if (K <= 0)
return -1;
for (i = 0; i < N; i++) {
for (j = i + 1; j < N; j++) {
if (str[i] == str[j])
str[j] = '\0';
}
if (str[i] != '\0')
distinct++;
if (distinct == K)
return str[i];
}
return -1;
}
// Driver code
public static void Main(String[] args)
{
String str = "GeeksForGeeks";
int K = 2;
int ans = printKDistinct(str.ToCharArray(), K);
if (ans == -1)
Console.WriteLine(-1);
else
Console.WriteLine((char)ans);
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// Javascript program to implement above approach
// Function to print the Kth distinct character
function printKDistinct(str, K) {
let distinct = 0, i, j, N = str.length;
if (K <= 0)
return -1;
for (i = 0; i < N; i++) {
for (j = i + 1; j < N; j++) {
if (str[i] == str[j])
str[j] = '\0';
}
if (str[i] != '\0')
distinct++;
if (distinct == K)
return str[i];
}
return -1;
}
// Driver code
let str = "GeeksForGeeks";
let K = 2;
let ans = printKDistinct(str, K);
if (ans == -1)
document.write(-1);
else
document.write(ans);
// This code is contributed by saurabh_jaiswal.
</script>
e
Complejidad temporal: O(N * N)
Espacio auxiliar: O(1)
Uso de conjuntos: un enfoque eficiente es usar conjuntos para almacenar caracteres recorriendo la string dada y verificando su tamaño en cada iteración. Si su tamaño se vuelve igual a K , devuelve el carácter actual. De lo contrario, K es mayor que el número de caracteres distintos presentes en la string, por lo que devuelve -1 .
A continuación se muestra la implementación del enfoque anterior.
C++14
// C++ program to implement the approach
#include <bits/stdc++.h>
using namespace std;
// Function to print the Kth distinct character
int printKDistinct(string& str, int& K)
{
set<int> unique;
int N = str.length();
for (int i = 0; i < N; i++) {
unique.insert(str[i]);
if (unique.size() == K)
return str[i];
}
return -1;
}
// Driver code
int main()
{
string str = "GeeksForGeeks";
int K = 2;
int ans = printKDistinct(str, K);
if (ans == -1)
cout << -1;
else
cout << (char)ans;
return 0;
}
Java
// Java code to implement the approach
import java.io.*;
import java.util.*;
class GFG
{
// Function to print the Kth distinct character
static int printKDistinct(String str, int K)
{
HashSet<Character> unique = new HashSet<>();
int N = str.length();
for (int i = 0; i < N; i++) {
unique.add(str.charAt(i));
if (unique.size() == K)
return str.charAt(i);
}
return -1;
}
// Driver code
public static void main(String[] args)
{
String str = "GeeksForGeeks";
int K = 2;
int ans = printKDistinct(str, K);
if (ans == -1)
System.out.println(-1);
else
System.out.println((char)ans);
}
}
// This code is contributed by Karandeep1234
Python3
# Python 3 program to implement the approach # Function to print the Kth distinct character def printKDistinct(st, K): unique = set([]) N = len(st) for i in range(N): unique.add(st[i]) if (len(unique) == K): return st[i] return -1 # Driver code if __name__ == "__main__": st = "GeeksForGeeks" K = 2 ans = printKDistinct(st, K) if (ans == -1): print(-1) else: print(ans) # This code is contributed by ukasp.
C#
// C# code to implement the approach
using System;
using System.Collections.Generic;
public class GFG
{
// Function to print the Kth distinct character
static int printKDistinct(String str, int K)
{
HashSet<char> unique = new HashSet<char>();
int N = str.Length;
for (int i = 0; i < N; i++) {
unique.Add(str[i]);
if (unique.Count == K)
return str[i];
}
return -1;
}
// Driver code
public static void Main(String[] args)
{
String str = "GeeksForGeeks";
int K = 2;
int ans = printKDistinct(str, K);
if (ans == -1)
Console.WriteLine(-1);
else
Console.WriteLine((char)ans);
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// JavaScript code for the above approach
// Function to print the Kth distinct character
function printKDistinct(str, K) {
let unique = new Set();
let N = str.length;
for (let i = 0; i < N; i++) {
unique.add(str[i]);
if (unique.size == K)
return str[i];
}
return -1;
}
// Driver code
let str = "GeeksForGeeks";
let K = 2;
let ans = printKDistinct(str, K);
if (ans == -1)
document.write(-1);
else
document.write(ans);
// This code is contributed by Potta Lokesh
</script>
e
Complejidad temporal: O(N * logN)
Espacio auxiliar: O(N)
Usando Hash-Mapa:Otra solución eficiente es usar Hashing . Siga los pasos que se mencionan a continuación:
- Cree una tabla hash vacía .
- Atraviese la string de entrada de izquierda a derecha y verifique si el carácter actual está presente en el mapa o no.
- Si no está presente en el mapa, incremente distinto .
- Si distinto se convierte en K , devuelve el carácter actual.
- Si K es mayor que el número de caracteres distintos presentes en la string, devuelve -1 .
A continuación se muestra la implementación del enfoque anterior.
C++14
// C++ program to implement the approach
#include <bits/stdc++.h>
using namespace std;
// Function to print the Kth distinct character
int printKDistinct(string& str, int& K)
{
int distinct = 0, N = str.length();
unordered_map<char, bool> freq;
for (int i = 0; i < N; i++) {
if (!freq[str[i]])
distinct++;
freq[str[i]] = 1;
if (distinct == K)
return str[i];
}
return -1;
}
// Driver code
int main()
{
string str = "GeeksForGeeks";
int K = 2;
int ans = printKDistinct(str, K);
if (ans == -1)
cout << -1;
else
cout << (char)ans;
return 0;
}
Python3
# Python program to implement the approach # Function to print the Kth distinct character def printKDistinct(Str, K): distinct,N = 0,len(Str) freq = dict() for i in range(N): if (Str[i] not in freq): distinct += 1 freq[Str[i]] = 1 if (distinct == K): return Str[i] return -1 # Driver code Str = "GeeksForGeeks" K = 2 ans = printKDistinct(Str, K) if (ans == -1): print(-1) else: print(ans) # This code is contributed by shinjanpatra
Javascript
<script>
// JavaScript program to implement the approach
// Function to print the Kth distinct character
const printKDistinct = (str, K) => {
let distinct = 0, N = str.length;
let freq = {};
for (let i = 0; i < N; i++) {
if (!freq[str[i]])
distinct++;
freq[str[i]] = 1;
if (distinct == K)
return str[i];
}
return -1;
}
// Driver code
let str = "GeeksForGeeks";
let K = 2;
let ans = printKDistinct(str, K);
if (ans == -1)
document.write(-1);
else
document.write(ans);
// This code is contributed by rakeshsahni
</script>
e
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por prophet1999 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA