统计美丽子字符串 I

标签: 字符串 枚举 前缀和

难度: Medium

给你一个字符串 s 和一个正整数 k 。

用 vowels 和 consonants 分别表示字符串中元音字母和辅音字母的数量。

如果某个字符串满足以下条件，则称其为 美丽字符串 ：

  • vowels == consonants，即元音字母和辅音字母的数量相等。
  • (vowels * consonants) % k == 0，即元音字母和辅音字母的数量的乘积能被 k 整除。

返回字符串 s 中 非空美丽子字符串 的数量。

子字符串是字符串中的一个连续字符序列。

英语中的 元音字母 为 'a'、'e'、'i'、'o' 和 'u' 。

英语中的 辅音字母 为除了元音字母之外的所有字母。

示例 1：

输入：s = "baeyh", k = 2
输出：2
解释：字符串 s 中有 2 个美丽子字符串。
- 子字符串 "baeyh"，vowels = 2（["a","e"]），consonants = 2（["y","h"]）。
可以看出字符串 "aeyh" 是美丽字符串，因为 vowels == consonants 且 vowels * consonants % k == 0 。
- 子字符串 "baeyh"，vowels = 2（["a","e"]），consonants = 2（["b","y"]）。
可以看出字符串 "baey" 是美丽字符串，因为 vowels == consonants 且 vowels * consonants % k == 0 。
可以证明字符串 s 中只有 2 个美丽子字符串。

示例 2：

输入：s = "abba", k = 1
输出：3
解释：字符串 s 中有 3 个美丽子字符串。
- 子字符串 "abba"，vowels = 1（["a"]），consonants = 1（["b"]）。
- 子字符串 "abba"，vowels = 1（["a"]），consonants = 1（["b"]）。
- 子字符串 "abba"，vowels = 2（["a","a"]），consonants = 2（["b","b"]）。
可以证明字符串 s 中只有 3 个美丽子字符串。

示例 3：

输入：s = "bcdf", k = 1
输出：0
解释：字符串 s 中没有美丽子字符串。

提示：

  • 1 <= s.length <= 1000
  • 1 <= k <= 1000
  • s 仅由小写英文字母组成。

Submission

运行时间: 50 ms

内存: 16.4 MB

class Solution:
    def beautifulSubstrings(self, s: str, k: int) -> int:
        
        
        
        # my solution ... 621 ms ... 79 % ... 16.5 MB ... 12 %
        #  time: O(n^2)
        # space: O(n)
        
        vowels = set('aeiou')
        v, f, res = 0, [], 0
        for j, ch in enumerate(s):
            if ch in vowels:
                v += 1
            f.append(v)
            for i in range(j-1, -1, -2):
                vcur = v
                if i:
                    vcur -= f[i-1]
                ccur = j - i + 1 - vcur
                if vcur == ccur and vcur * ccur % k == 0:
                    res += 1
        return res

Explain

该题解采用了一个遍历的方式来寻找所有可能的子字符串，并检查每个子字符串是否满足美丽字符串的条件。它首先使用一个集合来判断字符是否为元音。然后，使用一个列表 `f` 来记录从字符串开始到当前位置的元音字母的数量。对于每个字符位置 `j`，遍历所有可能的起始位置 `i`，计算从 `i` 到 `j` 的子字符串中的元音数和辅音数，进而检查这段子字符串是否满足美丽字符串的定义。通过两层循环遍历所有可能的子字符串，并通过一些简单的数学计算来判断子字符串是否满足条件。

时间复杂度: O(n^2)

空间复杂度: O(n)

class Solution:
    def beautifulSubstrings(self, s: str, k: int) -> int:
        # 初始化元音字母集合
        vowels = set('aeiou')
        # 初始化变量：v（当前元音计数），f（到每个位置的元音总数列表），res（结果计数）
        v, f, res = 0, [], 0
        # 遍历字符串的每个字符
        for j, ch in enumerate(s):
            # 如果字符是元音，更新元音计数
            if ch in vowels:
                v += 1
            # 将当前元音总数添加到列表
            f.append(v)
            # 对于每个字符位置 j，检查所有可能的子字符串
            for i in range(j-1, -1, -2):
                vcur = v # 当前位置的元音计数
                # 如果不是从第一个字符开始，调整元音计数
                if i:
                    vcur -= f[i-1]
                # 计算辅音数
                ccur = j - i + 1 - vcur
                # 判断是否是美丽字符串
                if vcur == ccur and vcur * ccur % k == 0:
                    res += 1
        return res

Explore

在题解中，列表`f`用于存储从字符串开始到当前位置的元音字母总数。为正确处理边界条件，应在遍历字符串之前初始化`f`为空列表，并在每次遍历字符时，更新并添加当前元音计数`v`到`f`中。初始元音计数`v`应设置为0，以确保从字符串的第一个字符开始计算时，元音字母的累计是正确的。每次字符判断后，`v`的值需要根据字符是否为元音进行更新，然后将这个更新后的值添加到`f`中。这样，`f`的每个元素`f[j]`就能准确地反映出从字符串开始到位置`j`的元音字母总数。

这种算法的空间复杂度主要由元音总数列表`f`决定，为`O(n)`，其中`n`是字符串`s`的长度。时间复杂度为`O(n^2)`，因为对于字符串中的每个位置`j`，算法都需要向前遍历以检查所有可能的子字符串。为优化此算法，可以考虑使用滑动窗口或哈希表来减少不必要的重复计算。例如，可以维护一个窗口内元音和辅音的计数，当窗口滑动时，只更新进入和离开窗口的字符计数，从而将时间复杂度降低到接近`O(n)`。

如果起始位置`i`为0，这表示子字符串从字符串`s`的起始位置开始，一直到位置`j`。在这种情况下，元音数直接由`f[j]`给出，因为`f[j]`存储的是从字符串开始到位置`j`的元音字母总数。辅音数则可以通过`j + 1 - f[j]`计算得出，这里`j + 1`是子字符串的总长度（因为索引是从0开始的），`f[j]`是元音的数量，两者的差就是辅音的数量。