3. 无重复字符的最长子串 难度:中等

题目描述:

给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。

示例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;
}
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

友情链接更多精彩内容