Dada una string str , la tarea es responder consultas Q donde cada consulta consta de dos números enteros L y R y tenemos que encontrar el primer carácter que no se repite en la substring str[L…R] . Si no hay ningún carácter que no se repita, imprima -1 .
Ejemplos:
Entrada: str = «GeeksForGeeks», q[] = {{0, 3}, {2, 3}, {5, 12}}
Salida:
G
e
F
La substring para las consultas es «Geek», «ek» y «ForGeeks» y sus primeros caracteres no repetidos son ‘G’, ‘e’ y ‘F’ respectivamente.Entrada: str = “xxyyxx”, q[] = {{2, 3}, {3, 4}}
Salida:
-1
y
Enfoque: Cree una array de frecuencia freq[][] donde freq[i][j] almacena la frecuencia del carácter en la substring str[0…j] cuyo valor ASCII es i . Ahora, la frecuencia de cualquier carácter en la substring str[i…j] cuyo valor ASCII es x se puede calcular como freq[x][j] = freq[x][i – 1] .
Ahora, para cada consulta, comience a recorrer la string en el rango dado, es decir, str[L…R] y para cada carácter, si su frecuencia es 1 , entonces este es el primer carácter que no se repite en la substring requerida. Si todos los caracteres tienen una frecuencia superior a 1 , imprima-1 .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Maximum distinct characters possible
#define MAX 256
// To store the frequency of the characters
int freq[MAX][MAX];
// Function to pre-calculate the frequency array
void preCalculate(string str, int n)
{
// Only the first character has
// frequency 1 till index 0
freq[(int)str[0]][0] = 1;
// Starting from the second
// character of the string
for (int i = 1; i < n; i++)
{
char ch = str[i];
// For every possible character
for (int j = 0; j < MAX; j++)
{
// Current character under consideration
char charToUpdate = j;
// If it is equal to the character
// at the current index
if (charToUpdate == ch)
freq[j][i] = freq[j][i - 1] + 1;
else
freq[j][i] = freq[j][i - 1];
}
}
}
// Function to return the frequency of the
// given character in the sub-string str[l...r]
int getFrequency(char ch, int l, int r)
{
if (l == 0)
return freq[(int)ch][r];
else
return (freq[(int)ch][r] -
freq[(int)ch][l - 1]);
}
// Function to return the first
// non-repeating character in range[l..r]
string firstNonRepeating(string str, int n,
int l, int r)
{
char t[2] = "";
// Starting from the first character
for (int i = l; i < r; i++)
{
// Current character
char ch = str[i];
// If frequency of the current character is 1
// then return the character
if (getFrequency(ch, l, r) == 1)
{
t[0] = ch;
return t;
}
}
// All the characters of the
// sub-string are repeating
return "-1";
}
// Driver code
int main()
{
string str = "GeeksForGeeks";
int n = str.length();
int queries[][2] = {{0, 3}, {2, 3}, {5, 12}};
int q = sizeof(queries) /
sizeof(queries[0]);
// Pre-calculate the frequency array
freq[MAX][n] = {0};
preCalculate(str, n);
for (int i = 0; i < q; i++)
cout << firstNonRepeating(str, n, queries[i][0],
queries[i][1])
<< endl;
return 0;
}
// This code is contributed by
// sanjeev2552
Java
// Java implementation of the approach
public class GFG {
// Maximum distinct characters possible
static final int MAX = 256;
// To store the frequency of the characters
static int freq[][];
// Function to pre-calculate the frequency array
static void preCalculate(String str, int n)
{
// Only the first character has
// frequency 1 till index 0
freq[(int)str.charAt(0)][0] = 1;
// Starting from the second
// character of the string
for (int i = 1; i < n; i++) {
char ch = str.charAt(i);
// For every possible character
for (int j = 0; j < MAX; j++) {
// Current character under consideration
char charToUpdate = (char)j;
// If it is equal to the character
// at the current index
if (charToUpdate == ch)
freq[j][i] = freq[j][i - 1] + 1;
else
freq[j][i] = freq[j][i - 1];
}
}
}
// Function to return the frequency of the
// given character in the sub-string str[l...r]
static int getFrequency(char ch, int l, int r)
{
if (l == 0)
return freq[(int)ch][r];
else
return (freq[(int)ch][r] - freq[(int)ch][l - 1]);
}
// Function to return the first non-repeating character in range[l..r]
static String firstNonRepeating(String str, int n, int l, int r)
{
// Starting from the first character
for (int i = l; i < r; i++) {
// Current character
char ch = str.charAt(i);
// If frequency of the current character is 1
// then return the character
if (getFrequency(ch, l, r) == 1)
return ("" + ch);
}
// All the characters of the
// sub-string are repeating
return "-1";
}
// Driver code
public static void main(String[] args)
{
String str = "GeeksForGeeks";
int n = str.length();
int queries[][] = { { 0, 3 }, { 2, 3 }, { 5, 12 } };
int q = queries.length;
// Pre-calculate the frequency array
freq = new int[MAX][n];
preCalculate(str, n);
for (int i = 0; i < q; i++) {
System.out.println(firstNonRepeating(str, n,
queries[i][0],
queries[i][1]));
}
}
}
Python3
# Python3 implementation of the approach # Maximum distinct characters possible MAX = 256 # To store the frequency of the characters freq = [[0 for i in range(MAX)] for j in range(MAX)] # Function to pre-calculate # the frequency array def preCalculate(string, n): # Only the first character has # frequency 1 till index 0 freq[ord(string[0])][0] = 1 # Starting from the second # character of the string for i in range(1, n): ch = string[i] # For every possible character for j in range(MAX): # Current character under consideration charToUpdate = chr(j) # If it is equal to the character # at the current index if charToUpdate == ch: freq[j][i] = freq[j][i - 1] + 1 else: freq[j][i] = freq[j][i - 1] # Function to return the frequency of the # given character in the sub-string str[l...r] def getFrequency(ch, l, r): if l == 0: return freq[ord(ch)][r] else: return (freq[ord(ch)][r] - freq[ord(ch)][l - 1]) # Function to return the first # non-repeating character in range[l..r] def firstNonRepeating(string, n, l, r): t = [""] * 2 # Starting from the first character for i in range(l, r): # Current character ch = string[i] # If frequency of the current character is 1 # then return the character if getFrequency(ch, l, r) == 1: t[0] = ch return t[0] # All the characters of the # sub-string are repeating return "-1" # Driver Code if __name__ == "__main__": string = "GeeksForGeeks" n = len(string) queries = [(0, 3), (2, 3), (5, 12)] q = len(queries) # Pre-calculate the frequency array preCalculate(string, n) for i in range(q): print(firstNonRepeating(string, n, queries[i][0], queries[i][1])) # This code is contributed by # sanjeev2552
C#
// C# implementation of the approach
using System;
class GFG
{
// Maximum distinct characters possible
static int MAX = 256;
// To store the frequency of the characters
static int [,]freq ;
// Function to pre-calculate the frequency array
static void preCalculate(string str, int n)
{
// Only the first character has
// frequency 1 till index 0
freq[(int)str[0],0] = 1;
// Starting from the second
// character of the string
for (int i = 1; i < n; i++)
{
char ch = str[i];
// For every possible character
for (int j = 0; j < MAX; j++)
{
// Current character under consideration
char charToUpdate = (char)j;
// If it is equal to the character
// at the current index
if (charToUpdate == ch)
freq[j,i] = freq[j,i - 1] + 1;
else
freq[j,i] = freq[j,i - 1];
}
}
}
// Function to return the frequency of the
// given character in the sub-string str[l...r]
static int getFrequency(char ch, int l, int r)
{
if (l == 0)
return freq[(int)ch, r];
else
return (freq[(int)ch, r] - freq[(int)ch, l - 1]);
}
// Function to return the first non-repeating character in range[l..r]
static string firstNonRepeating(string str, int n, int l, int r)
{
// Starting from the first character
for (int i = l; i < r; i++)
{
// Current character
char ch = str[i];
// If frequency of the current character is 1
// then return the character
if (getFrequency(ch, l, r) == 1)
return ("" + ch);
}
// All the characters of the
// sub-string are repeating
return "-1";
}
// Driver code
public static void Main()
{
string str = "GeeksForGeeks";
int n = str.Length;
int [,]queries = { { 0, 3 }, { 2, 3 }, { 5, 12 } };
int q = queries.Length;
// Pre-calculate the frequency array
freq = new int[MAX,n];
preCalculate(str, n);
for (int i = 0; i < q; i++)
{
Console.WriteLine(firstNonRepeating(str, n,
queries[i,0],
queries[i,1]));
}
}
}
// This code is contributed by AnkitRai01
Javascript
<script>
// Javascript implementation of the approach
// Maximum distinct characters possible
let MAX = 256;
// To store the frequency of the characters
let freq;
// Function to pre-calculate the frequency array
function preCalculate(str, n)
{
// Only the first character has
// frequency 1 till index 0
freq[str[0].charCodeAt()][0] = 1;
// Starting from the second
// character of the string
for (let i = 1; i < n; i++) {
let ch = str[i];
// For every possible character
for (let j = 0; j < MAX; j++) {
// Current character under consideration
let charToUpdate = String.fromCharCode(j);
// If it is equal to the character
// at the current index
if (charToUpdate == ch)
freq[j][i] = freq[j][i - 1] + 1;
else
freq[j][i] = freq[j][i - 1];
}
}
}
// Function to return the frequency of the
// given character in the sub-string str[l...r]
function getFrequency(ch, l, r)
{
if (l == 0)
return freq[ch.charCodeAt()][r];
else
return (freq[ch.charCodeAt()][r] - freq[ch.charCodeAt()][l - 1]);
}
// Function to return the first non-repeating character in range[l..r]
function firstNonRepeating(str, n, l, r)
{
// Starting from the first character
for (let i = l; i < r; i++) {
// Current character
let ch = str[i];
// If frequency of the current character is 1
// then return the character
if (getFrequency(ch, l, r) == 1)
return ("" + ch);
}
// All the characters of the
// sub-string are repeating
return "-1";
}
let str = "GeeksForGeeks";
let n = str.length;
let queries = [ [ 0, 3 ], [ 2, 3 ], [ 5, 12 ] ];
let q = queries.length;
// Pre-calculate the frequency array
freq = new Array(MAX);
for (let i = 0; i < MAX; i++)
{
freq[i] = new Array(n);
for (let j = 0; j < n; j++)
{
freq[i][j] = 0;
}
}
preCalculate(str, n);
for (let i = 0; i < q; i++) {
document.write(firstNonRepeating(str, n,
queries[i][0],
queries[i][1]) + "</br>");
}
</script>
Producción:
G e F