Queries to find the count of vowels in the substrings of the given string

0 0 9 minutes read

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 = “zambiatek”, 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 L^th character to the R^th 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 vowel
bool 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 code
int main()
{
    string str = "zambiatek";
    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 approach
class GFG
{
static int N = 2;
 
// Function that returns true
// if ch is a vowel
static 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 code
public static void main(String[] args) 
{
    String str = "zambiatek";
    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 = "zambiatek"; 
    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 approach
using System;
 
class GFG
{
static int N = 2;
 
// Function that returns true
// if ch is a vowel
static 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 code
public static void Main(String[] args) 
{
    String str = "zambiatek";
    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 = "zambiatek";
    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 vowel
bool 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 code
int main()
{
    string str = "zambiatek";
    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 approach
class GFG
{
static final int N = 2;
 
// Function that returns true
// if ch is a vowel
static 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 code
public static void main(String[] args)
{
    String str = "zambiatek";
    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 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')
 
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 code
if __name__ == '__main__':
    str1 = "zambiatek"
    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 approach
using System;
using System.Collections.Generic;
 
class GFG
{
static readonly int N = 2;
 
// Function that returns true
// if ch is a vowel
static 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 code
public static void Main(String[] args)
{
    String str = "zambiatek";
    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 approach
var 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 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 code
var str = "zambiatek";
var len = str.length;
var queries = [ [ 1, 3 ], [ 2, 4 ], [ 1, 9 ] ];
var q = queries.length
performQueries(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 zambiatek!