题目描述
给定一个字符串 s
,请你返回 两个相同字符之间的最长子字符串的长度,计算长度时不含这两个字符。如果不存在这样的子字符串,返回 -1
。
子字符串 是字符串中的一个连续字符序列。
样例
输入:s = "aa"
输出:0
解释:最优的子字符串是两个 'a' 之间的空子字符串。
输入:s = "abca"
输出:2
解释:最优的子字符串是 "bc"。
输入:s = "cbzxy"
输出:-1
解释:s 中不存在出现出现两次的字符,所以返回 -1。
输入:s = "cabbac"
输出:4
解释:最优的子字符串是 "abba" ,其他的非最优解包括 "bb" 和 ""。
限制
1 <= s.length <= 300
s
只含小写英文字母。
算法
(哈希表) $O(n)$
- 建立一个哈希表记录每个字符最早出现的位置。
- 遍历数组,如果当前字符不是第一次出现,那么用当前位置减去第一次出现的位置再减 1 来更新答案。
时间复杂度
- 遍历一次数组,故时间复杂度为 $O(n)$。
空间复杂度
- 仅需要常数的额外空间。
C++ 代码
class Solution {
public:
int maxLengthBetweenEqualCharacters(string s) {
vector<int> firstSeen(26, -1);
const int n = s.size();
int ans = -1;
for (int i = 0; i < n; i++) {
int c = s[i] - 'a';
if (firstSeen[c] == -1)
firstSeen[c] = i;
else
ans = max(ans, i - firstSeen[c] - 1);
}
return ans;
}
};