Given string str of length N and Q queries where every query consists of two integers L and R. For every query, the task is to find the count of vowels in the substring str[L…R].
Examples:
Input: str = “neveropen”, q[][] = {{1, 3}, {2, 4}, {1, 9}}
Output:
2
1
4
Query 1: “eek” has 2 vowels.
Query 2: “eks” has 1 vowel.
Query 3: “eeksforge” has 2 vowels.Input: str = “aaaa”, q[][] = {{1, 3}, {1, 4}}
Output:
3
3
Naive approach: For every query, traverse the string from the Lth character to the Rth character and find the count of vowels.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;#define N 2// Function that returns true// if ch is a vowelbool isVowel(char ch){ return (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u');}// Function to return the count of vowels// in the substring str[l...r]int countVowels(string str, int l, int r){ // To store the count of vowels int cnt = 0; // For every character in // the index range [l, r] for (int i = l; i <= r; i++) { // If the current character // is a vowel if (isVowel(str[i])) cnt++; } return cnt;}void performQueries(string str, int queries[][N], int q){ // For every query for (int i = 0; i < q; i++) { // Find the count of vowels // for the current query cout << countVowels(str, queries[i][0], queries[i][1]) << "\n"; }}// Driver codeint main(){ string str = "neveropen"; int queries[][N] = { { 1, 3 }, { 2, 4 }, { 1, 9 } }; int q = (sizeof(queries) / sizeof(queries[0])); performQueries(str, queries, q); return 0;} |
Java
// Java implementation of the approachclass GFG{static int N = 2;// Function that returns true// if ch is a vowelstatic boolean isVowel(char ch){ return (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u');}// Function to return the count of vowels// in the substring str[l...r]static int countVowels(String str, int l, int r){ // To store the count of vowels int cnt = 0; // For every character in // the index range [l, r] for (int i = l; i <= r; i++) { // If the current character // is a vowel if (isVowel(str.charAt(i))) cnt++; } return cnt;}static void performQueries(String str, int queries[][], int q){ // For every query for (int i = 0; i < q; i++) { // Find the count of vowels // for the current query System.out.println(countVowels(str, queries[i][0], queries[i][1])); }}// Driver codepublic static void main(String[] args) { String str = "neveropen"; int queries[][] = { { 1, 3 }, { 2, 4 }, { 1, 9 } }; int q = queries.length; performQueries(str, queries, q);}}// This code is contributed by PrinciRaj1992 |
Python3
# Python3 implementation of the approach N = 2; # Function that returns true # if ch is a vowel def isVowel(ch) : return (ch == 'a' or ch == 'e' or ch == 'i' or ch == 'o' or ch == 'u'); # Function to return the count of vowels # in the substring str[l...r] def countVowels(string, l, r) : # To store the count of vowels cnt = 0; # For every character in # the index range [l, r] for i in range(l, r + 1) : # If the current character # is a vowel if (isVowel(string[i])) : cnt += 1; return cnt; def performQueries(string, queries, q) : # For every query for i in range(q) : # Find the count of vowels # for the current query print(countVowels(string, queries[i][0], queries[i][1])); # Driver code if __name__ == "__main__" : string = "neveropen"; queries = [ [ 1, 3 ], [ 2, 4 ], [ 1, 9 ] ]; q = len(queries) performQueries(string, queries, q); # This code is contributed by AnkitRai01 |
C#
// C# implementation of the approachusing System;class GFG{static int N = 2;// Function that returns true// if ch is a vowelstatic Boolean isVowel(char ch){ return (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u');}// Function to return the count of vowels// in the substring str[l...r]static int countVowels(String str, int l, int r){ // To store the count of vowels int cnt = 0; // For every character in // the index range [l, r] for (int i = l; i <= r; i++) { // If the current character // is a vowel if (isVowel(str[i])) cnt++; } return cnt;}static void performQueries(String str, int [,]queries, int q){ // For every query for (int i = 0; i < q; i++) { // Find the count of vowels // for the current query Console.WriteLine(countVowels(str, queries[i, 0], queries[i, 1])); }}// Driver codepublic static void Main(String[] args) { String str = "neveropen"; int [,]queries = { { 1, 3 }, { 2, 4 }, { 1, 9 } }; int q = queries.GetLength(0); performQueries(str, queries, q);}}// This code is contributed by Rajput-Ji |
Javascript
<script> // Javascript implementation of the approach let N = 2; // Function that returns true // if ch is a vowel function isVowel(ch) { return (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u'); } // Function to return the count of vowels // in the substring str[l...r] function countVowels(str, l, r) { // To store the count of vowels let cnt = 0; // For every character in // the index range [l, r] for (let i = l; i <= r; i++) { // If the current character // is a vowel if (isVowel(str[i])) cnt++; } return cnt; } function performQueries(str, queries, q) { // For every query for (let i = 0; i < q; i++) { // Find the count of vowels // for the current query document.write(countVowels(str, queries[i][0], queries[i][1]) + "</br>"); } } let str = "neveropen"; let queries = [ [ 1, 3 ], [ 2, 4 ], [ 1, 9 ] ]; let q = queries.length; performQueries(str, queries, q);</script> |
Output:
2 1 4
Time Complexity: O(N * Q) where N is the length of a string and Q is the number of queries.
Auxiliary Space: O(1), no extra space is required, so it is a constant.
Efficient approach: Create a prefix array pre[] where pre[i] will store the count vowels in the substring str[0…i]. Now, the count of vowels in the range [L, R] can be easily calculated in O(1) as pre[R] – pre[L – 1].
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;#define N 2// Function that returns true// if ch is a vowelbool isVowel(char ch){ return (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u');}void performQueries(string str, int len, int queries[][N], int q){ // pre[i] will store the count of // vowels in the substring str[0...i] int pre[len]; if (isVowel(str[0])) pre[0] = 1; else pre[0] = 0; // Fill the pre[] array for (int i = 1; i < len; i++) { // If current character is a vowel if (isVowel(str[i])) pre[i] = 1 + pre[i - 1]; // If its a consonant else pre[i] = pre[i - 1]; } // For every query for (int i = 0; i < q; i++) { // Find the count of vowels // for the current query if (queries[i][0] == 0) { cout << pre[queries[i][1]] << "\n"; } else { cout << (pre[queries[i][1]] - pre[queries[i][0] - 1]) << "\n"; } }}// Driver codeint main(){ string str = "neveropen"; int len = str.length(); int queries[][N] = { { 1, 3 }, { 2, 4 }, { 1, 9 } }; int q = (sizeof(queries) / sizeof(queries[0])); performQueries(str, len, queries, q); return 0;} |
Java
// Java implementation of the approachclass GFG{static final int N = 2;// Function that returns true// if ch is a vowelstatic Boolean isVowel(char ch){ return (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u');}static void performQueries(String str, int len, int queries[][], int q){ // pre[i] will store the count of // vowels in the subString str[0...i] int []pre = new int[len]; if (isVowel(str.charAt(0))) pre[0] = 1; else pre[0] = 0; // Fill the pre[] array for (int i = 1; i < len; i++) { // If current character is a vowel if (isVowel(str.charAt(i))) pre[i] = 1 + pre[i - 1]; // If its a consonant else pre[i] = pre[i - 1]; } // For every query for (int i = 0; i < q; i++) { // Find the count of vowels // for the current query if (queries[i][0] == 0) { System.out.println(pre[queries[i][1]]); } else { System.out.println((pre[queries[i][1]] - pre[queries[i][0] - 1])); } }}// Driver codepublic static void main(String[] args){ String str = "neveropen"; int len = str.length(); int queries[][] = { { 1, 3 }, { 2, 4 }, { 1, 9 } }; int q = queries.length; performQueries(str, len, queries, q);}}// This code is contributed by Rajput-Ji |
Python 3
# Python 3 implementation of the approachN = 2# Function that returns true# if ch is a voweldef isVowel(ch): return (ch == 'a' or ch == 'e' or ch == 'i' or ch == 'o' or ch == 'u')def performQueries(str1, len1, queries, q): # pre[i] will store the count of # vowels in the substring str[0...i] pre = [0 for i in range(len1)] if (isVowel(str1[0])): pre[0] = 1 else: pre[0] = 0 # Fill the pre[] array for i in range(0, len1, 1): # If current character is a vowel if (isVowel(str1[i])): pre[i] = 1 + pre[i - 1] # If its a consonant else: pre[i] = pre[i - 1] # For every query for i in range(q): # Find the count of vowels # for the current query if (queries[i][0] == 0): print(pre[queries[i][1]]) else: print(pre[queries[i][1]] - pre[queries[i][0] - 1])# Driver codeif __name__ == '__main__': str1 = "neveropen" len1 = len(str1) queries = [[1, 3], [2, 4], [1, 9]] q = len(queries) performQueries(str1, len1, queries, q)# This code is contributed by Surendra_Gangwar |
C#
// C# implementation of the approachusing System;using System.Collections.Generic;class GFG{static readonly int N = 2;// Function that returns true// if ch is a vowelstatic Boolean isVowel(char ch){ return (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u');}static void performQueries(String str, int len, int [,]queries, int q){ // pre[i] will store the count of // vowels in the subString str[0...i] int []pre = new int[len]; if (isVowel(str[0])) pre[0] = 1; else pre[0] = 0; // Fill the pre[] array for (int i = 1; i < len; i++) { // If current character is a vowel if (isVowel(str[i])) pre[i] = 1 + pre[i - 1]; // If its a consonant else pre[i] = pre[i - 1]; } // For every query for (int i = 0; i < q; i++) { // Find the count of vowels // for the current query if (queries[i, 0] == 0) { Console.WriteLine(pre[queries[i, 1]]); } else { Console.WriteLine((pre[queries[i, 1]] - pre[queries[i, 0] - 1])); } }}// Driver codepublic static void Main(String[] args){ String str = "neveropen"; int len = str.Length; int [,]queries = { { 1, 3 }, { 2, 4 }, { 1, 9 } }; int q = queries.GetLength(0); performQueries(str, len, queries, q);}}// This code is contributed by Rajput-Ji |
Javascript
<script>// Javascript implementation of the approachvar N = 2;// Function that returns true// if ch is a vowelfunction isVowel(ch){ return (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u');}function performQueries(str, len, queries, q){ // pre[i] will store the count of // vowels in the substring str[0...i] var pre = Array(len); if (isVowel(str[0])) pre[0] = 1; else pre[0] = 0; // Fill the pre[] array for (var i = 1; i < len; i++) { // If current character is a vowel if (isVowel(str[i])) pre[i] = 1 + pre[i - 1]; // If its a consonant else pre[i] = pre[i - 1]; } // For every query for (var i = 0; i < q; i++) { // Find the count of vowels // for the current query if (queries[i][0] == 0) { document.write( pre[queries[i][1]] + "<br>"); } else { document.write(pre[queries[i][1]] - pre[queries[i][0] - 1] + "<br>"); } }}// Driver codevar str = "neveropen";var len = str.length;var queries = [ [ 1, 3 ], [ 2, 4 ], [ 1, 9 ] ];var q = queries.lengthperformQueries(str, len, queries, q);</script> |
Output:
2 1 4
Time Complexity: O(N) for pre-computation and O(1) for every query.
Auxiliary Space: O(N), where n is the length of the given 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!
