Given a string str consisting of N lowercase characters and an array Q[][] with each row of the form {l, r} representing a query. For each query, the task is to find the difference between the maximum frequency and minimum frequency of the characters in the substring {str[l], …. str[r]}.
Note: Consider 1 – based indexing.
Examples:
Input: N = 7, S = “abaabac”, Q[][] = {{ 2, 6 }, { 1, 7 }}
Output: 1 3
Explanation:
Query 1: ‘a’ occurs maximum number of times in the given range i.e., 3 and ‘b’ occurs minimum number of times in the given range i.e. 2. Therefore, output = 3 – 2 = 1.
Query 2: ‘a’ occurs maximum number of times in the given range i.e. 4 and ‘c’ occurs minimum number of times in the given range i.e. 1. Therefore, output = 4 – 1 = 3.Input: N = 6, S = “aabbcc”, Q[][] = {{1, 4}, {1, 6}}
Output: 0 0
Explanation:
Query 1: ‘a’ and ‘b’ both occurs same number of times in the given range. Therefore, the output is 0.
Query 2: All ‘a’, ‘b’ and ‘c’ occurs same number of times in the given range. Therefore, the output is 0.
Naive Approach: For each query, find the frequencies of all characters in the given range, and take the difference between the maximum and minimum frequencies.
Time Complexity: O((N + 26)* |Q|)
Auxiliary Space: O(26)
Below is the implementation of the above approach:
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> |
1 3
Efficient Approach: The idea is to use a 2D-Fenwick tree to store the frequency of each character. Follow the steps below to solve the problem:
- Create a two-dimensional Fenwick tree that stores the information about each character from ‘a’ to ‘z’.
- Then for each query, count the frequencies of each character in the given range using the Fenwick tree.
- From the frequencies found above, get the maximum and the minimum frequency.
- Print the difference between the maximum and minimum frequency as the answer.
Below is the implementation of the above approach:
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> |
1 3
Time Complexity: O(|Q| * log(N) * 26)
Auxiliary Space: O(N * 26)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!