leetcode 3.无重复字符的最长子串

题目:

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


示例 1:

输入: s = "abcabcbb"输出: 3解释:因为无重复字符的最长子串是"abc",所以其长度为 3。

示例 2:

输入: s = "bbbbb"输出: 1解释: 因为无重复字符的最长子串是"b",所以其长度为 1。

示例 3:

输入: s = "pwwkew"输出: 3解释: 因为无重复字符的最长子串是"wke",所以其长度为 3。     请注意,你的答案必须是子串 的长度,"pwke"是一个子序列,不是子串。

示例 4:

输入: s = ""输出: 0


提示:

0 <= s.length <= 5 * 104

s由英文字母、数字、符号和空格组成



解题思路:滑动窗口

起点(左窗口):left

向右拓展窗口:right

逐个向右扩展窗口( left<s.length( ) && right<s.length( ) ),若未遇到重复的字符,则right+1

若遇到重复的字符,删除left窗口同时扩展right窗口

计算窗口长度windowLength=right-left

取窗口长度的最大值maxLength=Math.max(maxLength,windowLength);


核心代码:

        while(left<s.length() && right<s.length() ){

            if(window.contains(s.charAt(right))){

                window.remove(s.charAt(left));

                left++;

            }else{

                window.add(s.charAt(right));

                right++;

                int windowLength=right-left;

                maxLength=Math.max(maxLength,windowLength);

            }

        }

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容