Dada una string S de tamaño N y consultas Q. Cada consulta consta de L y R ( 0 < = L < = R < N ) . La tarea es imprimir el carácter que ocurre la mayor cantidad de veces en el rango dado. Si hay varios caracteres que aparecen el máximo número de veces, imprima el menor lexicográficamente.
Nota : S consiste en letras minúsculas en inglés.
Ejemplos:
Entrada:
str = “geekss”,
Q = 2
0 2
3 5
Salida:
e
sEntrada:
str = “striver”,
Q = 3
0 1
1 6
5 6
Salida:
s
r
e
Enfoque ingenuo : un enfoque ingenuo consiste en iterar de L a R para cada consulta y encontrar el carácter que aparece el número máximo de veces utilizando una array de frecuencia de tamaño 26 .
Complejidad de tiempo : O(max(RL, 26)) por consulta, ya que usaremos un bucle para recorrer los tiempos de RL.
Espacio auxiliar: O(26), ya que usaremos espacio adicional para el arreglo de frecuencias.
Enfoque eficiente : un enfoque eficiente es usar una array de suma de prefijos para responder la consulta de manera eficiente. Let pre[i][j] almacena la aparición de un carácter j hasta el i -ésimo índice. Para cada consulta de aparición de un carácter j será pre[r][j] – pre[l-1][j] (si l > 0). Encuentra el carácter lexicográficamente más pequeño que aparece el máximo número de veces iterando las 26 letras minúsculas.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the sum of
// the addition of all possible subsets.
#include <bits/stdc++.h>
using namespace std;
// Function that answers all the queries
void solveQueries(string str, vector<vector<int> >& query)
{
// Length of the string
int len = str.size();
// Number of queries
int Q = query.size();
// Prefix array
int pre[len][26];
memset(pre, 0, sizeof pre);
// Iterate for all the characters
for (int i = 0; i < len; i++) {
// Increase the count of the character
pre[i][str[i] - 'a']++;
// Presum array for
// all 26 characters
if (i) {
// Update the prefix array
for (int j = 0; j < 26; j++)
pre[i][j] += pre[i - 1][j];
}
}
// Answer every query
for (int i = 0; i < Q; i++) {
// Range
int l = query[i][0];
int r = query[i][1];
int maxi = 0;
char c = 'a';
// Iterate for all characters
for (int j = 0; j < 26; j++) {
// Times the lowercase character
// j occurs till r-th index
int times = pre[r][j];
// Subtract the times it occurred
// till (l-1)th index
if (l)
times -= pre[l - 1][j];
// Max times it occurs
if (times > maxi) {
maxi = times;
c = char('a' + j);
}
}
// Print the answer
cout << "Query " << i + 1 << ": " << c << endl;
}
}
// Driver Code
int main()
{
string str = "striver";
vector<vector<int> > query;
query.push_back({ 0, 1 });
query.push_back({ 1, 6 });
query.push_back({ 5, 6 });
solveQueries(str, query);
}
Java
// Java program to find the sum of
// the addition of all possible subsets.
class GFG
{
// Function that answers all the queries
static void solveQueries(String str,
int[][] query)
{
// Length of the string
int len = str.length();
// Number of queries
int Q = query.length;
// Prefix array
int[][] pre = new int[len][26];
// Iterate for all the characters
for (int i = 0; i < len; i++)
{
// Increase the count of the character
pre[i][str.charAt(i) - 'a']++;
// Presum array for
// all 26 characters
if (i > 0)
{
// Update the prefix array
for (int j = 0; j < 26; j++)
pre[i][j] += pre[i - 1][j];
}
}
// Answer every query
for (int i = 0; i < Q; i++)
{
// Range
int l = query[i][0];
int r = query[i][1];
int maxi = 0;
char c = 'a';
// Iterate for all characters
for (int j = 0; j < 26; j++)
{
// Times the lowercase character
// j occurs till r-th index
int times = pre[r][j];
// Subtract the times it occurred
// till (l-1)th index
if (l > 0)
times -= pre[l - 1][j];
// Max times it occurs
if (times > maxi)
{
maxi = times;
c = (char)('a' + j);
}
}
// Print the answer
System.out.println("Query" + (i + 1) + ": " + c);
}
}
// Driver Code
public static void main(String[] args)
{
String str = "striver";
int[][] query = {{0, 1}, {1, 6}, {5, 6}};
solveQueries(str, query);
}
}
// This code is contributed by
// sanjeev2552
Python3
# Python3 program to find the sum of
# the addition of all possible subsets.
# Function that answers all the queries
def solveQueries(Str, query):
# Length of the String
ll = len(Str)
# Number of queries
Q = len(query)
# Prefix array
pre = [[0 for i in range(256)]
for i in range(ll)]
# memset(pre, 0, sizeof pre)
# Iterate for all the characters
for i in range(ll):
# Increase the count of the character
pre[i][ord(Str[i])] += 1
# Presum array for
# all 26 characters
if (i):
# Update the prefix array
for j in range(256):
pre[i][j] += pre[i - 1][j]
# Answer every query
for i in range(Q):
# Range
l = query[i][0]
r = query[i][1]
maxi = 0
c = 'a'
# Iterate for all characters
for j in range(256):
# Times the lowercase character
# j occurs till r-th index
times = pre[r][j]
# Subtract the times it occurred
# till (l-1)th index
if (l):
times -= pre[l - 1][j]
# Max times it occurs
if (times > maxi):
maxi = times
c = chr(j)
# Print the answer
print("Query ", i + 1, ": ", c)
# Driver Code
Str = "striver"
query = [[0, 1], [1, 6], [5, 6]]
solveQueries(Str, query)
# This code is contributed by Mohit Kumar
C#
// C# program to find the sum of
// the addition of all possible subsets.
using System;
class GFG
{
// Function that answers all the queries
static void solveQueries(String str,
int[,] query)
{
// Length of the string
int len = str.Length;
// Number of queries
int Q = query.GetLength(0);
// Prefix array
int[,] pre = new int[len, 26];
// Iterate for all the characters
for (int i = 0; i < len; i++)
{
// Increase the count of the character
pre[i, str[i] - 'a']++;
// Presum array for
// all 26 characters
if (i > 0)
{
// Update the prefix array
for (int j = 0; j < 26; j++)
pre[i, j] += pre[i - 1, j];
}
}
// Answer every query
for (int i = 0; i < Q; i++)
{
// Range
int l = query[i, 0];
int r = query[i, 1];
int maxi = 0;
char c = 'a';
// Iterate for all characters
for (int j = 0; j < 26; j++)
{
// Times the lowercase character
// j occurs till r-th index
int times = pre[r, j];
// Subtract the times it occurred
// till (l-1)th index
if (l > 0)
times -= pre[l - 1, j];
// Max times it occurs
if (times > maxi)
{
maxi = times;
c = (char)('a' + j);
}
}
// Print the answer
Console.WriteLine("Query" + (i + 1) + ": " + c);
}
}
// Driver Code
public static void Main(String[] args)
{
String str = "striver";
int[,] query = {{0, 1}, {1, 6}, {5, 6}};
solveQueries(str, query);
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// Javascript program to find the sum of
// the addition of all possible subsets.
// Function that answers all the queries
function solveQueries(str,query)
{
// Length of the string
let len = str.length;
// Number of queries
let Q = query.length;
// Prefix array
let pre = new Array(len);
for(let i=0;i<len;i++)
{
pre[i]=new Array(26);
for(let j=0;j<26;j++)
{
pre[i][j]=0;
}
}
// Iterate for all the characters
for (let i = 0; i < len; i++)
{
// Increase the count of the character
pre[i][str[i].charCodeAt(0) - 'a'.charCodeAt(0)]++;
// Presum array for
// all 26 characters
if (i > 0)
{
// Update the prefix array
for (let j = 0; j < 26; j++)
pre[i][j] += pre[i - 1][j];
}
}
// Answer every query
for (let i = 0; i < Q; i++)
{
// Range
let l = query[i][0];
let r = query[i][1];
let maxi = 0;
let c = 'a';
// Iterate for all characters
for (let j = 0; j < 26; j++)
{
// Times the lowercase character
// j occurs till r-th index
let times = pre[r][j];
// Subtract the times it occurred
// till (l-1)th index
if (l > 0)
times -= pre[l - 1][j];
// Max times it occurs
if (times > maxi)
{
maxi = times;
c = String.fromCharCode('a'.charCodeAt(0) + j);
}
}
// Print the answer
document.write("Query" + (i + 1) + ": " + c+"<br>");
}
}
// Driver Code
let str = "striver";
let query = [[0, 1], [1, 6], [5, 6]];
solveQueries(str, query);
// This code is contributed by unknown2108
</script>
Producción:
Query 1: s Query 2: r Query 3: e
Complejidad de tiempo: O (26 * N), ya que estamos usando bucles anidados para atravesar 26 * N veces. Donde N es la longitud de la string.
Espacio auxiliar: O(26*N), ya que estamos usando espacio extra para la array pre. Donde N es la longitud de la string.