DEV Community
·
1358. 包含所有三个字符的子串数量
💡
原文英文，约600词，阅读约需3分钟。
📝
内容提要
给定字符串s，使用滑动窗口和最后出现位置的方法，计算包含字符a、b、c的所有子串数量。通过遍历字符串并更新字符的最后出现索引，能够在O(n)时间复杂度内高效处理长字符串。
🎯
关键要点
- 给定字符串s，计算包含字符a、b、c的所有子串数量。
- 使用滑动窗口和最后出现位置的方法，能够在O(n)时间复杂度内高效处理长字符串。
- 示例1：输入s = 'abcabc'，输出为10。
- 示例2：输入s = 'aaacb'，输出为3。
- 示例3：输入s = 'abc'，输出为1。
- 需要维护字符'a'、'b'、'c'的最后出现索引。
- 一旦所有三个字符都出现过，计算这些索引的最小值。
- 有效子串的数量由最小索引加一得出。
- 该方法确保每个字符仅处理一次，适用于大输入规模。
❓
延伸问答
如何计算包含字符a、b、c的子串数量？
通过滑动窗口和最后出现位置的方法，遍历字符串并更新字符的最后出现索引，计算有效子串的数量。
给定字符串s = 'abcabc'，包含所有三个字符的子串数量是多少？
输出为10。
使用该方法处理长字符串的时间复杂度是多少？
该方法的时间复杂度为O(n)。
如何维护字符a、b、c的最后出现索引？
通过初始化last_a、last_b、last_c为-1，并在遍历字符串时更新这些索引。
示例字符串s = 'aaacb'的有效子串数量是多少？
输出为3。
如何计算有效子串的数量？
有效子串的数量由最小索引加一得出。
➡️
