LeetCode 题解工作台
不相交子字符串的最大数量
给你一个字符串 word 。 返回以 首尾字母相同 且 长度至少为 4 的 不相交子字符串 的最大数量。 子字符串 是字符串中连续的 非空 字符序列。 示例 1： 输入： word = "abcdeafdef" 输出： 2 解释： 两个子字符串是 "abcdea" 和 "fdef" 。 示例 2： …
4
题型
0
代码语言
3
相关题
当前训练重点
中等 · 状态·转移·动态规划
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你一个字符串 word。
返回以 首尾字母相同 且 长度至少为 4 的 不相交子字符串 的最大数量。
子字符串 是字符串中连续的 非空 字符序列。
示例 1：
输入： word = "abcdeafdef"
输出： 2
解释：
两个子字符串是 "abcdea" 和 "fdef"。
示例 2：
输入： word = "bcdaaaab"
输出： 1
解释：
唯一的子字符串是 "aaaa"。注意我们 不能 同时选择 "bcdaaaab"，因为它和另一个子字符串有重叠。
提示：
1 <= word.length <= 2 * 105word仅由小写英文字母组成。
解题思路
方法一
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) for precomputing character positions and expanding intervals, plus O(n log n) if intervals are sorted for DP. Space complexity is O(n) for storing intervals and DP tables. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Can you efficiently track all character occurrences for interval construction?
- question_mark
Is there a dynamic programming or greedy way to maximize non-overlapping selections?
- question_mark
How do you handle hidden overlaps when expanding intervals for each character?
常见陷阱
外企场景- error
Forgetting to expand intervals to cover all characters inside, leading to intersecting substrings.
- error
Assuming greedy selection by first appearance always yields the maximum number of substrings.
- error
Ignoring the minimum length constraint of four characters when collecting intervals.
进阶变体
外企场景- arrow_right_alt
Find maximum non-intersecting substrings without the minimum length restriction.
- arrow_right_alt
Return the actual substrings instead of the count.
- arrow_right_alt
Use a different character set, such as uppercase letters or digits, affecting hash table mapping.