描述

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

示例

示例 1:

  1. 输入: s = "abcabcbb"
  2. 输出: 3 
  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 由英文字母、数字、符号和空格组成

解题思路

  • 用类似 KMP 的滑窗方法，维护一个滑动窗口，用一个 hashMap 记录窗口中的字符和对应的地址，保证当前窗口，没有重复的字符。
  • 用一个变量 curLen 记录当前窗口的长度，用两个int 变量 start, end 分别记录窗口的左右端口。最后用一个 int 变量 res 维护最大长度。
  • 每一次窗口向右滑动时：
    • 对于新的字符，如果当前窗口中没有这个字符，那么更新 curLen 和 res 的值，同时也加入 hashMap 中，然后继续向右滑。
    • 如果是已经在窗口中的字符，根据 KMP 算法，我们将 start 指针更新为 重复的字符原先所在的地址加一的位置。并且将原来的 start 到现在的 start 之间的元素从 HashMap 中移除，然后更新 curLen 为 end - start + 1;

      代码

      class Solution {
public int lengthOfLongestSubstring(String s) {
   int res = Integer.MIN_VALUE;
   int n = s.length();
   if (n == 0) return 0;
   Map<Character, Integer> map = new HashMap<>();
   int start = 0, end = 0;
   int curLen = 0;
   while (end < n) {
       char curChar = s.charAt(end);
       if (!map.containsKey(curChar)) {
           map.put(curChar, end);
           curLen++;
           res = Math.max(res, curLen);
       } else {
           int nextStart = map.get(curChar) + 1;
           for (int i = start; i < nextStart; i++) {
               map.remove(s.charAt(i));
           }
           map.put(curChar, end);
           start = nextStart;
           curLen = end - start + 1;
       }
       end++;
   }
   return res == Integer.MIN_VALUE ? 0 : res;
}
}