计算给定字符串的所有子字符串中出现的元音数量

Question

我正在看这个挑战：

Given a string of length N of lowercase characters containing 0 or more vowels, the task is to find the count of vowels that occurred in all the substrings of the given string.

Example
Input: str = "abc" 
Output: 3
The given string "abc" contains only one vowel = 'a'. Substrings of "abc" are
{"a", "b", "c", "ab", "bc", "abc"}
Hence, the sum of occurrences of the vowel(s) in these strings is:
3 
('a' occurred 3 times).

如何在O(N)时间复杂度下解决上述问题？

Answer 1

以下是算法中要使用的一些元素：

让我们先数一数可以从一个字符串中形成多少子串（忽略元音计数）：

"a" => {"a"} => 1
"ab" => {"ab", "a", "b"} => 1+2 = 3
"abc" => {"abc", "ab", "bc", "a", "b", "c"} => 1+2+3 = 6
"abcd" => {"abcd", "abc", "bcd", "ab", "bc", "cd", "a", "b", "c", "d"} => 1+2+3+4 = 10
 ...

模式为1+2+3+...+，其中为字符串的长度，即(+1)/2

现在我们来看一个只有一个元音的字符串：“klmnopqrst”。然后答案包括计算具有该元音的子串的数量。

我们知道总共有 10(10+1)/2 = 55 个子串，但其中许多子串没有元音。 None 个“klmn”的子串有一个元音。有 4(4+1)/2 = 10 个这样的子串。 “pqrst”的 none 个子串也有一个元音。有 5(5+1)/2 = 15 个这样的子串。所有其他子串都有元音。所以我们可以做减法...输出应该是 55 - 10 - 15 = 30.

因此，一般原则是：对于输入中的每个元音，确定有多少子串不包含该元音——通过计算 [=31] 处的子串数量=]左，以及元音右处的那些。这为我们提供了有关 do 包含该元音的子字符串数量的线索——通过从子字符串总数中减去非大小写。

如果我们对每个元音都这样做，我们将计算出所有子字符串中元音的总出现次数。

这是用伪代码表示的算法：

function occurrence(str):
    n := length(str)
    total := 0
    allcount := n * (n + 1) // 2
    for i := 1 to n:
        if str[i] is a vowel:
            total = total + allcount - (i - 1) * i / 2 - (n - 1 - i) * (n - i) / 2
    return total

注意：请注意——正如在伪代码中常见的那样——i 是一个 position（从 1 开始），而不是从零开始的索引。

Answer 2

（以防不够用。）

每个元音出现在 (l + 1) * (r + 1) 个子字符串中，其中 l 是元音左侧的字符数，r 是元音右侧的字符数。

Example 1:

"abc"

'a': (0 + 1) * (2 + 1) = 3

Total: 3


Example 2:

"ae"

'a': (0 + 1) * (1 + 1) = 2
'e': (1 + 1) * (0 + 1) = 2

Total: 4

计算给定字符串的所有子字符串中出现的元音数量

Count the number of vowels occurring in all the substrings of given string

algorithm

dynamic-programming

data-structures

Example