Finding Subarrays of Vowels from a given String

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

The 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.

I have implemented the following algo for the above Problem.

    class Solution:
        # @param A : string
        # @return an integer
        def solve(self, A):
            x = ['a', 'e','i','o', 'u', 'A', 'E', 'I', 'O', 'U']
            y = []
            z = len(A)
            for i in A:
                if i in x:
                    n = A.index(i)
                    m = z
                    while m > n:
                        y.append(A[n:m])
                        m -= 1
            if y:
                return len(y)%10003
            else:
            return 0

Above Solution works fine for strings of normal length but not for greater length.

For example,

A = "pGpEusuCSWEaPOJmamlFAnIBgAJGtcJaMPFTLfUfkQKXeymydQsdWCTyEFjFgbSmknAmKYFHopWceEyCSumTyAFwhrLqQXbWnXSn"

Above Algo outputs 1630 subarrays but the expected answer is 1244.

Please help me improving the above algo. Thanks for the help

Answer

Focus on the required output: you do not need to find all of those substrings. All you need is the quantity of substrings.

Look again at your short example, ABEC. There are two vowels, A and E.

• A is at location 0. There are 4 total substrings, ending there and at each following location.
• E is at location 2. There are 2 total substrings, ending there and at each following location.

2+4 => 6

All you need do is to find the position of each vowel, subtract from the string length, and accumulate those differences:

A = "pGpEusuCSWEaPOJmamlFAnIBgAJGtcJaMPFTLfUfkQKXeymydQsdWCTyEFjFgbSmknAmKYFHopWceEyCSumTyAFwhrLqQXbWnXSn"

lenA = len(A)
vowel = "aeiouAEIOU"
count = 0

for idx, char in enumerate(A):
    if char in vowel:
       count += lenA - idx

print(count%10003)

Output:

1244

In a single command:

print( sum(len(A) - idx if char.lower() in "aeiou" else 0
       for idx, char in enumerate(A)) )