Amazing Subarrays Interviewbit Solution

Problem: Amazing Subarrays

Problem Statement:

You are given a string S, and you have to find all the amazing substrings of S.

Amazing Substring is one that starts with a vowel (a, e, i, o, u, A, E, I, O, U).

Input

Only argument given is string S. 

Output

Return a single integer X mod 10003, here X is number of Amazing Substrings in given string. 

Constraints

1 <= length(S) <= 1e6 
S can have special characters 

Example

Input
    ABEC

Output
    6

Explanation
	Amazing substrings of given string are :
	1. A
	2. AB
	3. ABE
	4. ABEC
	5. E
	6. EC
	here number of substrings are 6 and 6 % 10003 = 6.

Approach

The approach to this problem is pretty much straight forward, as we know the number of substring from ith index is N - i + 1, where N is the size of string.

So whenever we encounter a vowel, just add the the number of substrings to our result.

Time & Space Complexity

Time Complexity: O(N)
Space Complexity: O(1)

Solution

Code in C++