3557. 不相交子字符串的最大数量
题目描述
给你一个字符串 word。
返回以 首尾字母相同 且 长度至少为 4 的 不相交子字符串 的最大数量。
子字符串 是字符串中连续的 非空 字符序列。
示例 1：
输入： word = "abcdeafdef"
输出： 2
解释：
两个子字符串是 "abcdea" 和 "fdef"。
示例 2：
输入： word = "bcdaaaab"
输出： 1
解释：
唯一的子字符串是 "aaaa"。注意我们 不能 同时选择 "bcdaaaab"，因为它和另一个子字符串有重叠。
提示：
1 <= word.length <= 2 * 105word仅由小写英文字母组成。
解法
方法一
思考
子串须首尾同字母且长度至少 \(4\)，并两两不交，求最多个数。\(n \le 2 \cdot 10^5\)，不能枚举所有区间。
贪心从左扫描：对每个字母记录上一次可用的起点，一旦当前位置与该起点距离至少 \(3\) 即可收割一段并清空该字母的起点。先结束的短段不妨碍后面再选，个数最大。
1 | |
1 | |
1 | |
1 | |