1624.两个相同字符之间的最长子字符串

【LetMeFly】1624.两个相同字符之间的最长子字符串

力扣题目链接:https://leetcode.cn/problems/largest-substring-between-two-equal-characters/

给你一个字符串 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 <= 300
  • s 只含小写英文字母

方法一:存最大最小

开辟两个大小为26的数组,分别存放二十六个字母第一次出现、最后一次出现的位置。

一次遍历字符串,更新最大最小位置。

再遍历一次26个字母,对出现过的字母(出现位置不是开辟数组时设置的不在范围内的初始值),计算第一次出现位置和最后一次出现位置的间距。

  • 时间复杂度$O(n + C)$,其中$n$是字符串长度,$C$是字符集大小。本题中$C=26$
  • 空间复杂度$O(C)$

AC代码

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
int maxLengthBetweenEqualCharacters(string& s) {
int n = s.size();
vector<int> firstLoc(26, n);
vector<int> lastLoc(26, -1);
for (int i = 0; i < n; i++) {
int th = s[i] - 'a';
firstLoc[th] = min(firstLoc[th], i);
lastLoc[th] = max(lastLoc[th], i);
}
int ans = -1;
for (int i = 0; i < 26; i++) {
if (firstLoc[i] != n) {
ans = max(ans, lastLoc[i] - firstLoc[i] - 1);
}
}
return ans;
}
};

同步发文于CSDN,原创不易,转载请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/126900794


1624.两个相同字符之间的最长子字符串
https://blog.letmefly.xyz/2022/09/17/LeetCode 1624.两个相同字符之间的最长子字符串/
作者
Tisfy
发布于
2022年9月17日
许可协议