【2022-09-17每日一题】1624. 两个相同字符之间的最长子字符串
2022-09-17
2分钟阅读时长
2022-09-17每日一题：1624. 两个相同字符之间的最长子字符串
- 难度：Easy
- 标签：哈希表 、 字符串
给你一个字符串 s，请你返回 两个相同字符之间的最长子字符串的长度 ，计算长度时不含这两个字符。如果不存在这样的子字符串，返回 -1 。
子字符串 是字符串中的一个连续字符序列。
示例 1：
输入：s = "aa" 输出：0 解释：最优的子字符串是两个 'a' 之间的空子字符串。
示例 2：
输入：s = "abca" 输出：2 解释：最优的子字符串是 "bc" 。
示例 3：
输入：s = "cbzxy" 输出：-1 解释：s 中不存在出现出现两次的字符，所以返回 -1 。
示例 4：
输入：s = "cabbac" 输出：4 解释：最优的子字符串是 "abba" ，其他的非最优解包括 "bb" 和 "" 。
提示：
1 <= s.length <= 300s只含小写英文字母
方法一：哈希表
详细思路过程见官方题解，这里只做个人刷题记录，方便后续查询阅读
直接使用map
func maxLengthBetweenEqualCharacters(s string) int {
mp, ans := make(map[rune]int), -1
for i, c := range s {
if j, ok := mp[c]; ok {
ans = max(ans, i - j -1)
} else {
mp[c] = i
}
}
return ans
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
复杂度分析
时间复杂度：O(n)，其中 n 表示字符串的长度。我们只需遍历一遍字符串即可。
空间复杂度：O(n)，n 为不同字符个数。
使用26个长度数组
func maxLengthBetweenEqualCharacters(s string) int {
ans := -1
firstIndex := [26]int{}
for i := range firstIndex {
firstIndex[i] = -1
}
for i, c := range s {
c -= 'a'
if firstIndex[c] < 0 {
firstIndex[c] = i
} else {
ans = max(ans, i - firstIndex[c] - 1)
}
}
return ans
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
复杂度分析
时间复杂度：O(n)，其中 n 表示字符串的长度。我们只需遍历一遍字符串即可。
空间复杂度：O(∣Σ∣)，其中 Σ 是字符集，在本题中字符集为所有小写字母 ∣Σ∣=26。