题目描述:
给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。
示例1:
输入:s = "abcabcbb"
输出:3
解释:因为无重复字符的最长子串是"abc"
,所以其长度为 3。
示例2:
输入:s = "bbbbb"
输出:1
解释:因为无重复字符的最长子串是"b"
,所以其长度为 3。
示例3:
输入:s = "pwwkew"
输出:3
解释:因为无重复字符的最长子串是"wke"
,所以其长度为 3。
请注意,你的答案必须是 子串 的长度,"pwke"
是一个子序列,不是子串。
示例4:
输入:s = ""
输出:0
提示
0 <= s.length <= 5 * 10^4
-
s
由英文字母、数字、符号和空格组成
思路
滑动窗口
代码示例:
int lengthOfLongestSubstring(char * s){
int occ[256] = {0}; //初始化全0,在子串中出现置1
int ans = 0, len = 0, rk = -1, i = 0;
int n = strlen(s);
for(; i < n; i ++) {
if(i != 0) {
occ[s[i - 1]] --; //在occ中去掉滑动前子串的第一个字符
len --;
}
while(rk + 1 < n && !occ[s[rk + 1]]) { //下一个字符是否在子串中出现过
rk ++;
occ[s[rk]] ++;
len ++;
}
if(len > ans) {
ans = len;
}
}
return ans;
}