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.

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 Complexity: O(N)
 Space Complexity: O(1)

Code in C++