Dada una string str que consta de N caracteres en minúsculas y una array Q[][] con cada fila de la forma {l, r} que representa una consulta. Para cada consulta, la tarea es encontrar la diferencia entre la frecuencia máxima y la frecuencia mínima de los caracteres en la substring {str[l], …. string[r]} .
Nota: Considere la indexación basada en 1 .
Ejemplos:
Entrada: N = 7, S = “abaabac”, Q[][] = {{ 2, 6 }, { 1, 7 }}
Salida: 1 3
Explicación:
Consulta 1: ‘a’ ocurre el número máximo de veces en el rango dado, es decir, 3 y ‘b’ ocurre el número mínimo de veces en el rango dado, es decir, 2. Por lo tanto, salida = 3 – 2 = 1.
Consulta 2: ‘a’ ocurre el número máximo de veces en el rango dado, es decir, 4 y ‘ c’ ocurre el número mínimo de veces en el rango dado, es decir, 1. Por lo tanto, salida = 4 – 1 = 3.Entrada: N = 6, S = “aabbcc”, Q[][] = {{1, 4}, {1, 6}}
Salida: 0 0
Explicación:
Consulta 1: ‘a’ y ‘b’ ocurren igual número de veces en el rango dado. Por lo tanto, la salida es 0.
Consulta 2: Todos los ‘a’, ‘b’ y ‘c’ ocurren la misma cantidad de veces en el rango dado. Por lo tanto, la salida es 0.
Enfoque ingenuo: para cada consulta, encuentre las frecuencias de todos los caracteres en el rango dado y tome la diferencia entre las frecuencias máxima y mínima.
Complejidad temporal: O((N + 26)* |Q|)
Espacio auxiliar: O(26)
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find difference between maximum and
// minimum frequency of a character in given range
void maxDiffFreq(vector<pair<int, int> > queries,
string S)
{
// Stores length of string
int N = S.size();
// Stores count of queries
int Q = queries.size();
// Iterate over the characters
// of the string
for (int i = 0; i < Q; ++i) {
// Stores l-value of a query
int l = queries[i].first - 1;
// Stores r-value of a query
int r = queries[i].second - 1;
int freq[26] = { 0 };
// Store count of every character
// laying in range [l, r]
for (int j = l; j <= r; j++) {
// Update frequency of
// current character
freq[S[j] - 'a']++;
}
// Stores maximum frequency
// of characters in given range
int mx = 0;
// Stores minimum frequency
// of characters in given range
int mn = 99999999;
// Iterate over all possible characters
// of the given string
for (int j = 0; j < 26; j++) {
// Update mx
mx = max(mx, freq[j]);
// If (j + 'a') is present
if (freq[j])
mn = min(mn, freq[j]);
}
// difference between max and min
cout << mx - mn << endl;
}
}
// Driver Code
int main()
{
// Given string
string S = "abaabac";
// Given queries
vector<pair<int, int> > queries{ { 2, 6 }, { 1, 7 } };
// Function Call
maxDiffFreq(queries, S);
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to find difference between maximum and
// minimum frequency of a character in given range
static void maxDiffFreq(int [][]queries,
String S)
{
// Stores length of String
int N = S.length();
// Stores count of queries
int Q = queries.length;
// Iterate over the characters
// of the String
for (int i = 0; i < Q; ++i)
{
// Stores l-value of a query
int l = queries[i][0] - 1;
// Stores r-value of a query
int r = queries[i][1] - 1;
int freq[] = new int[26];
// Store count of every character
// laying in range [l, r]
for (int j = l; j <= r; j++) {
// Update frequency of
// current character
freq[S.charAt(j) - 'a']++;
}
// Stores maximum frequency
// of characters in given range
int mx = 0;
// Stores minimum frequency
// of characters in given range
int mn = 99999999;
// Iterate over all possible characters
// of the given String
for (int j = 0; j < 26; j++) {
// Update mx
mx = Math.max(mx, freq[j]);
// If (j + 'a') is present
if (freq[j]>0)
mn = Math.min(mn, freq[j]);
}
// difference between max and min
System.out.print(mx - mn +"\n");
}
}
// Driver Code
public static void main(String[] args)
{
// Given String
String S = "abaabac";
// Given queries
int [][]queries = { { 2, 6 }, { 1, 7 } };
// Function Call
maxDiffFreq(queries, S);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python 3 program for the above approach
# Function to find difference between maximum
# and minimum frequency of a character in
# given range
def maxDiffFreq(queries, S):
# Stores length of string
N = len(S)
# Stores count of queries
Q = len(queries)
# Iterate over the characters
# of the string
for i in range(Q):
# Stores l-value of a query
l = queries[i][0] - 1
# Stores r-value of a query
r = queries[i][1] - 1
freq = [0] * 26
# Store count of every character
# laying in range [l, r]
for j in range(l, r + 1):
# Update frequency of
# current character
freq[ord(S[j]) - ord('a')] += 1
# Stores maximum frequency
# of characters in given range
mx = 0
# Stores minimum frequency
# of characters in given range
mn = 99999999
# Iterate over all possible characters
# of the given string
for j in range(26):
# Update mx
mx = max(mx, freq[j])
# If (j + 'a') is present
if (freq[j]):
mn = min(mn, freq[j])
# Difference between max and min
print(mx - mn)
# Driver Code
if __name__ == "__main__":
# Given string
S = "abaabac"
# Given queries
queries = [ [ 2, 6 ], [ 1, 7 ] ]
# Function Call
maxDiffFreq(queries, S)
# This code is contributed by chitranayal
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to find difference between maximum and
// minimum frequency of a character in given range
static void maxDiffFreq(List<Tuple<int, int>> queries, string S)
{
// Stores length of string
int N = S.Length;
// Stores count of queries
int Q = queries.Count;
// Iterate over the characters
// of the string
for (int i = 0; i < Q; ++i)
{
// Stores l-value of a query
int l = queries[i].Item1 - 1;
// Stores r-value of a query
int r = queries[i].Item2 - 1;
int[] freq = new int[26];
// Store count of every character
// laying in range [l, r]
for (int j = l; j <= r; j++)
{
// Update frequency of
// current character
freq[S[j] - 'a']++;
}
// Stores maximum frequency
// of characters in given range
int mx = 0;
// Stores minimum frequency
// of characters in given range
int mn = 99999999;
// Iterate over all possible characters
// of the given string
for (int j = 0; j < 26; j++)
{
// Update mx
mx = Math.Max(mx, freq[j]);
// If (j + 'a') is present
if (freq[j] != 0)
mn = Math.Min(mn, freq[j]);
}
// difference between max and min
Console.WriteLine(mx - mn);
}
}
// Driver code
static void Main()
{
// Given string
string S = "abaabac";
// Given queries
List<Tuple<int, int>> queries = new List<Tuple<int, int>>();
queries.Add(new Tuple<int, int>(2, 6));
queries.Add(new Tuple<int, int>(1, 7));
// Function Call
maxDiffFreq(queries, S);
}
}
// This code is contributed by divyeshrabadiya07
Javascript
<script>
// Javascript program for the above approach
// Function to find difference between maximum and
// minimum frequency of a character in given range
function maxDiffFreq(queries, S)
{
// Stores length of string
let N = S.length;
// Stores count of queries
let Q = queries.length;
// Iterate over the characters
// of the string
for(let i = 0; i < Q; ++i)
{
// Stores l-value of a query
let l = queries[i][0] - 1;
// Stores r-value of a query
let r = queries[i][1] - 1;
let freq = new Array(26).fill(0);
// Store count of every character
// laying in range [l, r]
for(let j = l; j <= r; j++)
{
// Update frequency of
// current character
freq[S[j].charCodeAt(0) -
'a'.charCodeAt(0)]++;
}
// Stores maximum frequency
// of characters in given range
let mx = 0;
// Stores minimum frequency
// of characters in given range
let mn = 99999999;
// Iterate over all possible characters
// of the given string
for(let j = 0; j < 26; j++)
{
// Update mx
mx = Math.max(mx, freq[j]);
// If (j + 'a') is present
if (freq[j])
mn = Math.min(mn, freq[j]);
}
// Difference between max and min
document.write(mx - mn + "<br>");
}
}
// Driver Code
// Given string
let S = "abaabac";
// Given queries
let queries = [ [ 2, 6 ], [ 1, 7 ] ];
// Function Call
maxDiffFreq(queries, S);
// This code contributed by _saurabh_jaiswal
</script>
Producción:
1 3
Enfoque eficiente: la idea es utilizar un árbol 2D-Fenwick para almacenar la frecuencia de cada carácter . Siga los pasos a continuación para resolver el problema:
- Cree un árbol Fenwick bidimensional que almacene la información sobre cada carácter de la ‘a’ a la ‘z’ .
- Luego, para cada consulta, cuente las frecuencias de cada carácter en el rango dado usando el árbol de Fenwick .
- De las frecuencias encontradas arriba, obtenga la frecuencia máxima y mínima.
- Imprime la diferencia entre la frecuencia máxima y mínima como respuesta.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to update frequency of
// a character in Fenwick tree
void update(int BIT[26][10005], int idx,
int i, int val)
{
while (i < 10005) {
// Update frequency of (idx + 'a')
BIT[idx][i] += val;
// Update i
i = i + (i & (-i));
}
}
// Function to find the frequency of
// a character (idx + 'a') in range [1, i]
int query(int BIT[26][10005], int idx, int i)
{
// Stores frequency of character, (idx + 'a')
// in range [1, i]
int ans = 0;
while (i > 0) {
// Update ans
ans += BIT[idx][i];
// Update i
i = i - (i & (-i));
}
return ans;
}
// Function to find difference between maximum and
// minimum frequency of a character in given range
void maxDiffFreq(string s, vector<pair<int, int> > queries)
{
// BIT[i][j]: Stores frequency of (i + 'a')
// If j is a power of 2, then it stores
// the frequency (i + 'a') of from [1, j]
int BIT[26][10005];
// Stores length of string
int n = s.size();
// Iterate over the characters
// of the string
for (int i = 0; i < n; i++) {
// Update the frequency of
// s[i] in fenwick tree
update(BIT, s[i] - 'a', i + 1, 1);
}
// Stores count of queries
int Q = queries.size();
// Iterate over all the queries
for (int i = 0; i < Q; ++i) {
// Stores maximum frequency of
// a character in range [l, r]
int mx = 0;
// Stores minimum frequency of
// a character in range [l, r]
int mn = INT_MAX;
int l = queries[i].first;
int r = queries[i].second;
// Iterate over all possible characters
for (int j = 0; j < 26; j++) {
// Stores frequency of (j + 'a')
// in range [1, r]
int p = query(BIT, j, r);
// Stores frequency of (j + 'a')
// in range [1, l - 1]
int q = query(BIT, j, l - 1);
// Update mx
mx = max(mx, p - q);
// If a character (i + 'a') present
// in range [l, r]
if (p > 0) {
// Update mn
mn = min(mn, p - q);
}
}
// Print the difference between
// max and min freq
cout << mx - mn << endl;
}
}
// Driver Code
int main()
{
// Given string
string S = "abaabac";
// Given queries
vector<pair<int, int> > queries
= { { 2, 6 }, { 1, 7 } };
// Function Call
maxDiffFreq(S, queries);
}
Java
// Java program for the above approach
import java.util.*;
class GFG
{
// Function to update frequency of
// a character in Fenwick tree
static void update(int BIT[][], int idx,
int i, int val)
{
while (i < 10005)
{
// Update frequency of (idx + 'a')
BIT[idx][i] += val;
// Update i
i = i + (i & (-i));
}
}
// Function to find the frequency of
// a character (idx + 'a') in range [1, i]
static int query(int BIT[][], int idx, int i)
{
// Stores frequency of character, (idx + 'a')
// in range [1, i]
int ans = 0;
while (i > 0) {
// Update ans
ans += BIT[idx][i];
// Update i
i = i - (i & (-i));
}
return ans;
}
// Function to find difference between maximum and
// minimum frequency of a character in given range
static void maxDiffFreq(String s, int [][]queries)
{
// BIT[i][j]: Stores frequency of (i + 'a')
// If j is a power of 2, then it stores
// the frequency (i + 'a') of from [1, j]
int[][] BIT = new int[26][10005];
// Stores length of String
int n = s.length();
// Iterate over the characters
// of the String
for (int i = 0; i < n; i++) {
// Update the frequency of
// s[i] in fenwick tree
update(BIT, s.charAt(i) - 'a', i + 1, 1);
}
// Stores count of queries
int Q = queries.length;
// Iterate over all the queries
for (int i = 0; i < Q; ++i) {
// Stores maximum frequency of
// a character in range [l, r]
int mx = 0;
// Stores minimum frequency of
// a character in range [l, r]
int mn = Integer.MAX_VALUE;
int l = queries[i][0];
int r = queries[i][1];
// Iterate over all possible characters
for (int j = 0; j < 26; j++) {
// Stores frequency of (j + 'a')
// in range [1, r]
int p = query(BIT, j, r);
// Stores frequency of (j + 'a')
// in range [1, l - 1]
int q = query(BIT, j, l - 1);
// Update mx
mx = Math.max(mx, p - q);
// If a character (i + 'a') present
// in range [l, r]
if (p > 0) {
// Update mn
mn = Math.min(mn, p - q);
}
}
// Print the difference between
// max and min freq
System.out.print(mx - mn +"\n");
}
}
// Driver Code
public static void main(String[] args)
{
// Given String
String S = "abaabac";
// Given queries
int [][]queries
= { { 2, 6 }, { 1, 7 } };
// Function Call
maxDiffFreq(S, queries);
}
}
// This code is contributed by shikhasingrajput
Python3
# Python3 program for the above approach
import sys
# Function to update frequency of
# a character in Fenwick tree
def update(BIT, idx, i, val) :
while (i < 10005) :
# Update frequency of (idx + 'a')
BIT[idx][i] += val
# Update i
i = i + (i & (-i))
# Function to find the frequency of
# a character (idx + 'a') in range [1, i]
def query(BIT, idx, i) :
# Stores frequency of character, (idx + 'a')
# in range [1, i]
ans = 0
while (i > 0) :
# Update ans
ans += BIT[idx][i]
# Update i
i = i - (i & (-i))
return ans
# Function to find difference between maximum and
# minimum frequency of a character in given range
def maxDiffFreq(s, queries) :
# BIT[i][j]: Stores frequency of (i + 'a')
# If j is a power of 2, then it stores
# the frequency (i + 'a') of from [1][j]
BIT = [[0 for i in range(10005)] for j in range(26)]
# Stores length of String
n = len(s)
# Iterate over the characters
# of the String
for i in range(n) :
# Update the frequency of
# s[i] in fenwick tree
update(BIT, ord(s[i]) - ord('a'), i + 1, 1)
# Stores count of queries
Q = len(queries)
# Iterate over all the queries
for i in range(Q) :
# Stores maximum frequency of
# a character in range [l, r]
mx = 0
# Stores minimum frequency of
# a character in range [l, r]
mn = sys.maxsize
l = queries[i][0]
r = queries[i][1]
# Iterate over all possible characters
for j in range(26) :
# Stores frequency of (j + 'a')
# in range [1, r]
p = query(BIT, j, r)
# Stores frequency of (j + 'a')
# in range [1, l - 1]
q = query(BIT, j, l - 1)
# Update mx
mx = max(mx, p - q)
# If a character (i + 'a') present
# in range [l, r]
if (p > 0) :
# Update mn
mn = min(mn, p - q)
# Print the difference between
# max and min freq
print(mx - mn)
# Given String
S = "abaabac"
# Given queries
queries = [ [ 2, 6 ], [ 1, 7 ] ]
# Function Call
maxDiffFreq(S, queries)
# This code is contributed by divyesh072019.
C#
// C# program for the above approach
using System;
public class GFG
{
// Function to update frequency of
// a character in Fenwick tree
static void update(int [,]BIT, int idx,
int i, int val)
{
while (i < 10005)
{
// Update frequency of (idx + 'a')
BIT[idx,i] += val;
// Update i
i = i + (i & (-i));
}
}
// Function to find the frequency of
// a character (idx + 'a') in range [1, i]
static int query(int [,]BIT, int idx, int i)
{
// Stores frequency of character, (idx + 'a')
// in range [1, i]
int ans = 0;
while (i > 0)
{
// Update ans
ans += BIT[idx,i];
// Update i
i = i - (i & (-i));
}
return ans;
}
// Function to find difference between maximum and
// minimum frequency of a character in given range
static void maxDiffFreq(String s, int [,]queries)
{
// BIT[i,j]: Stores frequency of (i + 'a')
// If j is a power of 2, then it stores
// the frequency (i + 'a') of from [1, j]
int[,] BIT = new int[26, 10005];
// Stores length of String
int n = s.Length;
// Iterate over the characters
// of the String
for (int i = 0; i < n; i++)
{
// Update the frequency of
// s[i] in fenwick tree
update(BIT, s[i] - 'a', i + 1, 1);
}
// Stores count of queries
int Q = queries.GetLength(0);
// Iterate over all the queries
for (int i = 0; i < Q; ++i)
{
// Stores maximum frequency of
// a character in range [l, r]
int mx = 0;
// Stores minimum frequency of
// a character in range [l, r]
int mn = int.MaxValue;
int l = queries[i, 0];
int r = queries[i, 1];
// Iterate over all possible characters
for (int j = 0; j < 26; j++)
{
// Stores frequency of (j + 'a')
// in range [1, r]
int p = query(BIT, j, r);
// Stores frequency of (j + 'a')
// in range [1, l - 1]
int q = query(BIT, j, l - 1);
// Update mx
mx = Math.Max(mx, p - q);
// If a character (i + 'a') present
// in range [l, r]
if (p > 0)
{
// Update mn
mn = Math.Min(mn, p - q);
}
}
// Print the difference between
// max and min freq
Console.Write(mx - mn +"\n");
}
}
// Driver Code
public static void Main(String[] args)
{
// Given String
String S = "abaabac";
// Given queries
int [,]queries
= { { 2, 6 }, { 1, 7 } };
// Function Call
maxDiffFreq(S, queries);
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// Javascript program for the above approach
// Function to update frequency of
// a character in Fenwick tree
function update(BIT, idx, i, val)
{
while (i < 10005)
{
// Update frequency of (idx + 'a')
BIT[idx][i] += val;
// Update i
i = i + (i & (-i));
}
}
// Function to find the frequency of
// a character (idx + 'a') in range [1, i]
function query(BIT, idx, i)
{
// Stores frequency of character, (idx + 'a')
// in range [1, i]
let ans = 0;
while (i > 0)
{
// Update ans
ans += BIT[idx][i];
// Update i
i = i - (i & (-i));
}
return ans;
}
// Function to find difference between maximum and
// minimum frequency of a character in given range
function maxDiffFreq(s, queries)
{
// BIT[i][j]: Stores frequency of (i + 'a')
// If j is a power of 2, then it stores
// the frequency (i + 'a') of from [1, j]
let BIT = new Array(26);
for(let i = 0; i < 26; i++)
{
BIT[i] = new Array(10005);
for(let j = 0; j < 10005; j++)
{
BIT[i][j] = 0;
}
}
// Stores length of String
let n = s.length;
// Iterate over the characters
// of the String
for(let i = 0; i < n; i++)
{
// Update the frequency of
// s[i] in fenwick tree
update(BIT, s[i].charCodeAt(0) -
'a'.charCodeAt(0),
i + 1, 1);
}
// Stores count of queries
let Q = queries.length;
// Iterate over all the queries
for(let i = 0; i < Q; ++i)
{
// Stores maximum frequency of
// a character in range [l, r]
let mx = 0;
// Stores minimum frequency of
// a character in range [l, r]
let mn = Number.MAX_VALUE;
let l = queries[i][0];
let r = queries[i][1];
// Iterate over all possible characters
for(let j = 0; j < 26; j++)
{
// Stores frequency of (j + 'a')
// in range [1, r]
let p = query(BIT, j, r);
// Stores frequency of (j + 'a')
// in range [1, l - 1]
let q = query(BIT, j, l - 1);
// Update mx
mx = Math.max(mx, p - q);
// If a character (i + 'a') present
// in range [l, r]
if (p > 0)
{
// Update mn
mn = Math.min(mn, p - q);
}
}
// Print the difference between
// max and min freq
document.write(mx - mn + "<br>");
}
}
// Driver Code
let S = "abaabac";
// Given queries
let queries = [ [ 2, 6 ], [ 1, 7 ] ];
// Function Call
maxDiffFreq(S, queries);
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
1 3
Complejidad de tiempo: O(|Q| * log(N) * 26)
Espacio auxiliar: O(N * 26)
Publicación traducida automáticamente
Artículo escrito por ankitkumar0000333 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA