腾讯常规算法测试题：最长无重复字符子串

给定一个字符串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;
}