Finding Subarrays of Vowels from a given String

Question

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.

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.

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 1

将重点放在所需的输出上：您无需查找所有这些子字符串。您所需要的只是子串的数量。

再次查看您的简短示例ABEC。有两个元音，A和E。

• A 在位置0。总共有4个子字符串，在此位置以及随后的每个位置结束。
• E 在位置2。总共有2个子字符串，在此结束并在随后的每个位置结束。

2 + 4 => 6

您需要做的就是找到每个元音的位置，从字符串长度中减去，然后累加这些差异：

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)

输出：

1244

在一个命令中：

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