Queries to calculate difference between the frequencies of the most and least occurring characters in specified substring

// 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 

// 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