M3557.不相交子字符串的最大数量

greedy, https://leetcode.cn/problems/find-maximum-number-of-non-intersecting-substrings/description/

给你一个字符串 word。

返回以 首尾字母相同 且 长度至少为 4 的 不相交子字符串 的最大数量。

子字符串 是字符串中连续的 非空 字符序列。

示例 1：

输入： word = "abcdeafdef"

输出： 2

解释：

两个子字符串是 "abcdea" 和 "fdef"。

示例 2：

输入： word = "bcdaaaab"

输出： 1

解释：

唯一的子字符串是 "aaaa"。注意我们 不能 同时选择 "bcdaaaab"，因为它和另一个子字符串有重叠。

提示：

• 1 <= word.length <= 2 * 10^5
• word 仅由小写英文字母组成。

from collections import defaultdict

class Solution:
    def maxSubstrings(self, word: str) -> int:
        pos = defaultdict(list)

        # 收集每个字符的所有位置
        for i, ch in enumerate(word):
            pos[ch].append(i)

        # 存储所有符合条件的子串 [start, end]
        intervals = []

        for ch in pos:
            indices = pos[ch]
            n = len(indices)
            for i in range(n):
                for j in range(i + 1, n):
                    if indices[j] - indices[i] + 1 >= 4:
                        intervals.append((indices[i], indices[j]))
                        break  # 找到最小的满足条件的就停止内层循环，避免重复

        # 按照结束位置排序，方便贪心选择不重叠区间
        intervals.sort(key=lambda x: x[1])

        res = 0
        last_end = -1

        for start, end in intervals:
            if start > last_end:
                res += 1
                last_end = end

        return res

if __name__ == "__main__":
    sol = Solution()
    print(sol.maxSubstrings("abcdeafdef"))
    print(sol.maxSubstrings("bcdaaaab"))
    print(sol.maxSubstrings("aabececbbeccdcdcbbdece"))