题目说明
请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符串的长度。
假设字符串中只包含从’a’到’z’的字符。
样例
输入:"abcabc"
输出:3
算法1
(双指针++类似离散化)
和最长连续不重复子序列实质上是一样的,只不过在这里我把字符串映射成了int型的。
有一个很坑的地方就在于st[]数组在函数内使用的时候需要先memset(st,0,len)一下。
时间复杂度
$O(n)$
C++ 代码
class Solution {
public:
int longestSubstringWithoutDuplication(string s) {
//定义区间 i,j之前的元素没有重复
int a[100010];
int len=0;
for(auto x:s){
a[len++]=x-'a';
}
int st[100];
memset(st,0,30);
int res=0;
for(int i=0,j=0;i<len;i++){
st[a[i]]++;
while(st[a[i]]>1){
st[a[j]]--;
j++;
}
res=max(res,i-j+1);
}
return res;
}
};