Given a string str[] of length N of lowercase characters containing 0 or more vowels, the task is to find the count of vowels that occurred in all the substrings of the given string.
Examples:
Input: str = “abc”
Output: 3
The given string “abc” contains only one vowel = ‘a’
Substrings of “abc” are = {“a”, “b”, “c”, “ab”, “bc, “abc”}
Hence, the sum of occurrences of the vowel in these strings = 3.(‘a’ occurred 3 times)Input: str = “daceh”
Output: 16
Prefix Sum Approach: The Naive Approach and the approach using prefix sum are discussed in the Set 1 of this article.
Efficient Approach: Suppose, given string is str, substring starts from position x, and ends at position y and if the vowel are at i-th position, where 0<=x<=i and i<=y<-N . for each vowel, it could be in the substring, that is (i+1) choices for x and (n-i) choices for y. So there are total (i+1)*(n-i) substrings containing str[i]. Take a constant “aeiou“. Follow the steps below to solve the problem:
- Initialize the variable res as 0 to store the answer.
- Iterate over the range [0, N) using the variable i and perform the following tasks:
- If str[i] is a vowel then add the value of (I+1)*(N-i) to the variable res to count the total number of vowels possible.
- After performing the above steps, print the value of res as the answer.
Below is the implementation of the above approach.
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to count the number of vowelslong long countVowels(string str){ // Define the size of the string // and ans as zero long res = 0, N = str.size(); // Start traversing and find if their // is any vowel or not for (int i = 0; i < N; ++i) // If there is vowel, then count // the numbers of vowels if (string("aeiou").find(str[i]) != string::npos) res += (i + 1) * (N - i); return res;}// Driver Codeint main(){ string str = "daceh"; // Call the function long long ans = countVowels(str); cout << ans << endl; return 0;} |
Java
// Java program for the above approachclass GFG{ // Function to count the number of vowels static long countVowels(String str) { // Define the size of the String // and ans as zero long res = 0, N = str.length(); // Start traversing and find if their // is any vowel or not for (int i = 0; i < N; ++i) // If there is vowel, then count // the numbers of vowels if (new String("aeiou").contains(String.valueOf(str.charAt(i)))) res += (i + 1) * (N - i); return res; } // Driver Code public static void main(String[] args) { String str = "daceh"; // Call the function long ans = countVowels(str); System.out.print(ans +"\n"); }}// This code is contributed by shikhasingrajput. |
Python3
# Python program for the above approach# Function to count the number of vowelsdef countVowels(str): # Define the size of the String # and ans as zero res = 0; N = len(str); # Start traversing and find if their # is any vowel or not for i in range(N): # If there is vowel, then count # the numbers of vowels if ((str[i]) in ("aeiou")): res += (i + 1) * (N - i); return res;# Driver Codeif __name__ == '__main__': str = "daceh"; # Call the function ans = countVowels(str); print(ans);# This code is contributed by 29AjayKumar |
C#
// C# program for the above approachusing System;class GFG{ // Function to count the number of vowels static long countVowels(String str) { // Define the size of the String // and ans as zero long res = 0, N = str.Length; // Start traversing and find if their // is any vowel or not for (int i = 0; i < N; ++i) // If there is vowel, then count // the numbers of vowels if (new String("aeiou").Contains(str[i])) res += (i + 1) * (N - i); return res; } // Driver Code public static void Main() { String str = "daceh"; // Call the function long ans = countVowels(str); Console.Write(ans +"\n"); }}// This code is contributed by gfgking |
Javascript
<script>// javascript program for the above approach // Function to count the number of vowels function countVowels(str) { // Define the size of the String // and ans as zero var res = 0, N = str.length; // Start traversing and find if their // is any vowel or not for (var i = 0; i < N; ++i) // If there is vowel, then count // the numbers of vowels if ("aeiou".includes(str[i])) res += (i + 1) * (N - i); return res; }// Driver Codevar str = "daceh";// Call the functionvar ans = countVowels(str);document.write(ans);// This code is contributed by shikhasingrajput </script> |
16
Time Complexity: O(N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!