腾讯常考十道算法真题：无重复字符的最长子串

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

示例 1:

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

示例 2:

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

这道题可以使用滑动窗口来实现。滑动窗口就是维护一个窗口，不断滑动，然后更新答案。

滑动窗口的大致逻辑框架，伪代码如下：

int left =0，right = 0;
while (right < s.size()){
  //增大窗口
  window.add(s[right]);
  right++;
  
  while (window needs shrink){
    //缩小窗口
    window.remove (s[left]);
    left ++;
  }
}

解法流程如下：

• 首先呢，就是获取原字符串的长度。
• 接着维护一个窗口（数组、哈希、队列）
• 窗口一步一步向右扩展
• 窗口在向右扩展滑动过程，需要判断左边是否需要缩减
• 最后比较更新答案

完整代码如下：

int lengthOfLongestSubstring(String s){
     //获取原字符串的长度
     int len = s.length();
     //维护一个哈希集合的窗口
     Set<Character> windows = new HashSet<>();
     int left=0,right =0;
     int res =0;

     while(right<len){
       char c = s.charAt(right);
       //窗口右移
       right++;

       //判断是否左边窗口需要缩减，如果已经包含，那就需要缩减
       while(windows.contains(c)){
          windows.remove(s.charAt(left));
           left++;
       }
       windows.add(c);
       //比较更新答案
       res = Math.max(res,windows.size());
      }
     return res;
}