LeetCode 1624. 两个相同字符之间的最长子字符串
目录
题目描述
题意分析
给定一个小写字母字符串，找出两个相同字符之间的最长子串长度并返回；如果不存在任何一对相同字符，返回 -1。
「之间」这个词是全题唯一的坑：要求的是两个相同字符夹住的中间部分，不包含这两个字符本身。所以若两个相同字符位于下标
i和j，答案是j - i - 1而不是j - i + 1。相邻的两个相同字符（如"aa"）夹出的是空串，长度为 0——注意 0 是一个合法答案，与「不存在」的 -1 完全不同。无解时返回 -1 而不是 0，这决定了答案变量必须以 -1 起步，且不能用「答案是否大于 0」来判断有没有解。
字符集只有 26 个小写字母，字符串长度上限 300。规模小到怎么写都能过，但这也意味着考点不在效率而在边界的准确性。
定长字符集是个明确信号：所有「按字符统计」的结构都可以用长度 26 的数组代替哈希表，访问更快、代码更短。
边界上，长度为 0 或 1 的字符串必然返回 -1；全部字符互不相同时也返回 -1。
解法：记录首尾位置
核心思路
对同一个字符，要让两个端点之间的距离最大，左端点应取它的首次出现位置，右端点应尽可能靠后。因此扫描时只需永久保存每个字符的首次位置；后续每次遇到该字符，都把当前位置当作当前最右端点计算长度。
两个相同字符位于下标
first和i时，中间子字符串不包含端点，长度为i - first - 1。字符集只有 26 个小写字母，使用长度为 26 的数组比哈希表更直接。数组以
-1表示尚未出现，因为下标 0 是合法位置；答案也从-1开始，以区分“没有重复字符”和合法长度 0。不变量：扫描到下标
i后，first[c]是字符c的最早出现位置；answer是右端点不超过i的所有相同字符对中的最大间隔。正确性：对任意字符，固定右端点时与最早位置配对一定最长；扫描会把它的每个后续位置都作为右端点，因而最终包含首尾位置形成的全局最大间隔。再对全部字符取最大值，即为答案。
解题步骤
- 将 26 个首次位置全部初始化为
-1，答案初始化为-1。- 从左到右扫描字符；若首次出现，记录当前位置且以后不覆盖。
- 若已经出现过，用
i - first[c] - 1更新答案。
s = "abca"中，a的首次位置为 0，再次出现在 3，间隔为 2；s = "aa"的合法答案为 0；所有字符互不相同时答案保持-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。
关键点总结
- 最大间隔只需要每个字符的最早位置与扫描到的最晚位置。
- 首次位置一旦记录就不能覆盖，否则会退化成相邻出现间距。
- “两个字符之间”不含端点，长度公式必须减 1。
- 合法答案 0 与无解
-1不同，初始化要准确表达两种状态。
易错点总结
- 长度写成
i - first：会多算一个端点；"aa"应返回 0。- 不断覆盖首次位置：只能得到相邻两次出现的间隔，可能漏掉首尾最大值。
- 答案初始化为 0：没有任何重复字符时会错误返回 0。
- 首次位置初始化为 0：无法区分未出现与出现在下标 0。
- 使用
i - first + 1：这是包含两端的区间长度，与题意相差 2。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 763. 划分字母区间 | 中等 | 同样先记录每个字母的最后出现位置，再用它做贪心切分 |
| 387. 字符串中的第一个唯一字符 | 简单 | 用定长计数数组找只出现一次的字符，判据从首末相等换成频次为 1 |
| 219. 存在重复元素 II | 简单 | 关注的是相邻两次出现的最小间距，与本题的首末最大间距正好相反 |
| 3. 无重复字符的最长子串 | 中等 | 同样靠「上次出现位置」推进，但要维护滑动窗口而非全局首末 |
| 187. 重复的DNA序列 | 中等 | 同为记录字符片段的出现情况，但键是定长子串且需要判断出现次数 |
| 409. 最长回文串 | 简单 | 同为字符频次统计题，重点在成对字符与落单字符的组合规则 |