Given a string S of size N and Q queries. Every query consists of L and R ( 0 < = L < = R < N ) . The task is to print the character that occurs the maximum number of times in the given range. If there are multiple characters that occur maximum number of times then print the lexicographically smallest of them.
Note: S consists of lowercase English letters.
Examples:
Input:
str = “neveropens”,
Q = 2
0 2
3 5
Output:
e
sInput:
str = “striver”,
Q = 3
0 1
1 6
5 6
Output:
s
r
e
Naive Approach: A naive approach is to iterate from L to R for every query and find the character that appears the maximum number of times using frequency array of size 26.
Time Complexity: O(max(R-L, 26)) per query, as we will be using a loop to traverse R-L times.
Auxiliary Space: O(26), as we will be using extra space for frequency array.
Efficient Approach: An efficient approach is to use a prefix sum array to efficiently answer the query. Let pre[i][j] stores the occurrence of a character j till the i-th index. For every query occurrence of a character j will be pre[r][j] – pre[l-1][j](if l > 0). Find the lexicographically smallest character that appears the maximum number of times by iterating the 26 lowercase letters.
Below is the implementation of the above approach:
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 queriesvoid 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 Codeint 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 queriesdef 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 CodeStr = "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 queriesfunction 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 Codelet str = "striver";let query = [[0, 1], [1, 6], [5, 6]];solveQueries(str, query);// This code is contributed by unknown2108</script> |
Output:
Query 1: s Query 2: r Query 3: e
Time Complexity: O(26*N), as we are using nested loops for traversing 26*N times. Where N is the length of the string.
Auxiliary Space: O(26*N), as we are using extra space for the matrix pre. Where N is the length of the string.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
