Given a string S of length N and an array Q[][] of queries in the form {l, r, y}. For each query, the task is to print the number of characters y present in the range [l, r].
Examples:
Input: S = “aabv”, Q[][] = {{0, 3, ‘a’}, {1, 2, ‘b’}}
Output: 2 1
Explanation:
Query 1: Number of character ‘a’ present in the range [0, 3] is 2.
Query 2: Number of character ‘b’ present in the range [1, 2] is 1.Input: S = “abcd”, Q[][] = {{1, 3, ‘c’}, {1, 1, ‘b’}}
Output: 1 1
Explanation:
Query 1: Number of character ‘c’ present in the range [1, 3] is 1.
Query 2: Number of character ‘b’ present in the range [1, 1] is 1.
Naive Approach: The simplest approach is to traverse the string over the range [l, r] and increment the counter by 1 if the character at index i is equal to y for each query {l, r, y}. After traversing, print the counter for each query.
Time Complexity: O(N*Q)
Auxiliary Space: O(N)
Efficient Approach: The idea is to pre-compute the number of characters present in the range 1 to i for each character from ‘a’ to ‘z’ where 1 ? i ? N using Prefix Sum technique. Follow the steps below to solve the problem:
- Initialize an array dp[N+1][26] where dp[i][j] stores the number of characters (i+’a’) present in the range [0, i].
- Now, Precompute the number of each character present in the range [1, i] where 1 ? i ? N by incrementing dp[i][j] by dp[i – 1][j] where 0 ? j < 26 and increment dp[i][S[j] – ‘a’] by 1.
- For each query {l, r, y}, print the value of dp[r][y – ‘a’] – dp[l – 1][y – ‘a’] as the number of characters y present in the range [l, r].
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include<bits/stdc++.h>using namespace std;// Function to print count of char// y present in the range [l, r]void noOfChars(string s, char queries[][3], int q){ // Length of the string int n = s.length(); // Stores the precomputed results int dp[n + 1][26]; memset(dp, 0, sizeof(dp)); // Iterate the given string for(int i = 0; i < n; i++) { // Increment dp[i][y-'a'] by 1 dp[i + 1][s[i]-'a']++; // Pre-compute for(int j = 0; j < 26; j++) { dp[i + 1][j] += dp[i][j]; } } // Traverse each query for(int i = 0; i < q; i++) { int l = (int)queries[i][0]; int r = (int)queries[i][1]; int c = queries[i][2] - 'a'; // Print the result for // each query cout << dp[r] - dp[l - 1] << " "; }}// Driver Codeint main() { // Given string string S = "aabv"; // Given Queries char queries[2][3] = {{ 1, 2, 'a' },{ 2, 3, 'b' }}; // Function Call noOfChars(S, queries, 2); return 0;}// This code is contributed by avanitrachhadiya2155 |
Java
// Java program for the above approachimport java.io.*;class GFG { // Function to print count of char // y present in the range [l, r] static void noOfChars(String s, char[][] queries) { // Length of the string int n = s.length(); // Stores the precomputed results int dp[][] = new int[n + 1][26]; // Iterate the given string for (int i = 0; i < n; i++) { // Increment dp[i][y-'a'] by 1 dp[i + 1][s.charAt(i) - 'a']++; // Pre-compute for (int j = 0; j < 26; j++) { dp[i + 1][j] += dp[i][j]; } } // Number of queries int q = queries.length; // Traverse each query for (int i = 0; i < q; i++) { int l = (int)queries[i][0]; int r = (int)queries[i][1]; int c = queries[i][2] - 'a'; // Print the result for // each query System.out.print( dp[r] - dp[l - 1] + " "); } } // Driver Code public static void main(String[] args) { // Given string String S = "aabv"; // Given Queries char queries[][] = new char[][] { { 1, 2, 'a' }, { 2, 3, 'b' } }; // Function Call noOfChars(S, queries); }} |
Python3
# Python3 program for the above approach# Function to print count of char# y present in the range [l, r]def noOfChars(s, queries): # Length of the string n = len(s) # Stores the precomputed results dp = [[0 for i in range(26)] for i in range(n + 1)] # Iterate the given string for i in range(n): # Increment dp[i][y-'a'] by 1 dp[i + 1][ord(s[i]) - ord('a')] += 1 # Pre-compute for j in range(26): dp[i + 1][j] += dp[i][j] # Number of queries q = len(queries) # Traverse each query for i in range(q): l = queries[i][0] r = queries[i][1] c = ord(queries[i][2]) - ord('a') # Print the result for # each query print(dp[r] - dp[l - 1], end = " ") # Driver Codeif __name__ == '__main__': # Given string S = "aabv" # Given Queries queries = [ [ 1, 2, 'a' ], [ 2, 3, 'b' ] ] # Function Call noOfChars(S, queries)# This code is contributed by mohit kumar 29 |
C#
// C# program for the above approachusing System;public class GFG { // Function to print count of char // y present in the range [l, r] static void noOfChars(String s, char[,] queries) { // Length of the string int n = s.Length; // Stores the precomputed results int [,]dp = new int[n + 1, 26]; // Iterate the given string for (int i = 0; i < n; i++) { // Increment dp[i,y-'a'] by 1 dp[i + 1, s[i] - 'a']++; // Pre-compute for (int j = 0; j < 26; j++) { dp[i + 1, j] += dp[i, j]; } } // Number of queries int q = queries.GetLength(0); // Traverse each query for (int i = 0; i < q; i++) { int l = (int)queries[i, 0]; int r = (int)queries[i, 1]; int c = queries[i, 2] - 'a'; // Print the result for // each query Console.Write( dp[r, c] - dp[l - 1, c] + " "); } } // Driver Code public static void Main(String[] args) { // Given string String S = "aabv"; // Given Queries char [,]queries = new char[,] { { (char)1, (char)2, 'a' }, { (char)2, (char)3, 'b' } }; // Function Call noOfChars(S, queries); }}// This code is contributed by 29AjayKumar |
Javascript
<script>// JavaScript program for the above approach // Function to print count of char// y present in the range [l, r]function noOfChars(s,queries){ // Length of the string var n = s.length; // Stores the precomputed results var dp = Array(n+1).fill(0).map(x => Array(26).fill(0)); // Iterate the given string for (var i = 0; i < n; i++) { // Increment dp[i][y-'a'] by 1 dp[i + 1][s.charAt(i).charCodeAt(0) - 'a'.charCodeAt(0)]++; // Pre-compute for (var j = 0; j < 26; j++) { dp[i + 1][j] += dp[i][j]; } } // Number of queries var q = queries.length; // Traverse each query for (var i = 0; i < q; i++) { var l = String.fromCharCode(queries[i][0]).charCodeAt(0); var r = String.fromCharCode(queries[i][1]).charCodeAt(0); var c = queries[i][2].charCodeAt(0) - 'a'.charCodeAt(0); // Print the result for // each query document.write( dp[r] - dp[l - 1] + " "); }}// Driver Code // Given stringvar S = "aabv";// Given Queriesvar queries = [ [ 1, 2, 'a' ], [ 2, 3, 'b' ] ];// Function CallnoOfChars(S, queries);// This code contributed by shikhasingrajput </script> |
Output:
2 1
Time Complexity: O(Q+N*26)
Auxiliary Space: O(N)
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!
