Problem: Amazing Subarrays
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).
Only argument given is string S.
Return a single integer X mod 10003, here X is number of Amazing Substrings in given string.
1 <= length(S) <= 1e6 S can have special characters
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 & Space Complexity
Time Complexity: O(N) Space Complexity: O(1)
Code in C++