LeetCode 1624. 两个相同字符之间的最长子字符串
题目描述
题意分析
找到两个相同字符作为边界，求它们中间连续片段的最大长度，不包含边界字符。中间内容没有额外限制，所以只需要比较边界下标；不存在相同字符对时返回
-1。
解法：首次位置 + 右端点扫描
核心思路
[!blue]
从左到右枚举右端点i，用first[c]保存字符c最早出现的位置。固定i后，合法左端点越靠前，中间长度i - first[c] - 1就越大，因此只需和最早的相同字符配对。第一次遇到字符时记下下标，之后遇到它只更新答案，不覆盖首次位置。任意最优字符对的右端点都会被扫描到，而最早位置给出的长度至少不小于这对字符的长度，所以不会漏掉最优解。
题目只含 $26$ 个小写字母，使用定长数组即可。首次位置初始化为
-1，与合法下标 $0$ 区分；答案也初始化为-1，表示还没有找到字符对。两个相同字符相邻时，中间片段为空，但长度 $0$ 仍是合法答案。
解题步骤
- 首次位置全部初始化为 -1。
- 答案初始化为
-1，依次扫描字符；首次遇到时只记录下标。- 再次遇到时计算排除端点后的长度，更新答案。
- 返回答案。只有一个字符或所有字符互不相同时，不会产生候选，答案保持
-1。
代码实现
class Solution {
public int maxLengthBetweenEqualCharacters(String s) {
int[] first = new int[26];
for (int i = 0; i < first.length; i++) {
first[i] = -1;
}
// 无相同字符对时返回负一，相邻相同字符的合法答案为零。
int answer = -1;
for (int i = 0; i < s.length(); i++) {
int index = s.charAt(i) - 'a';
// 只保存最早位置，后续匹配才能得到最大间隔。
if (first[index] == -1) {
first[index] = i;
} else {
answer = Math.max(answer, i - first[index] - 1);
}
}
return answer;
}
}
func maxLengthBetweenEqualCharacters(s string) int {
first := make([]int, 26)
for i := range first {
first[i] = -1
}
// 无相同字符对时返回负一，相邻相同字符的合法答案为零。
answer := -1
for i := 0; i < len(s); i++ {
index := int(s[i] - 'a')
// 只保存最早位置，后续匹配才能得到最大间隔。
if first[index] == -1 {
first[index] = i
} else if distance := i - first[index] - 1; distance > answer {
answer = distance
}
}
return answer
}
复杂度分析
- 时间复杂度：$O(n)$，扫描一次。
- 空间复杂度：$O(1)$，固定 26 个字符位置。
关键点总结
[!green]
- 最早位置不能覆盖，它决定后续最大间隔。
- 长度公式减一，排除两个端点。
- 无解 -1 与合法空串长度 0 不同。
易错点总结
[!yellow]
- 每次覆盖位置：退化成只比较相邻两次出现。
- 答案从 0 开始：无重复字符时会误报有解。
- 使用包含端点的长度公式：把端点算进子串。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 325. 和等于 k 的最长子数组长度 | 中等 | 同样为某种状态保留最早出现位置以最大化跨度，本题状态是边界字符，原题是前缀和。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！