题目

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

示例 1:

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

示例 2:

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

示例 3:

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

提示：

  • 0 <= s.length <= 5 * 104
  • s 由英文字母、数字、符号和空格组成

实现代码

和【力扣76】最小覆盖字串思路一样，使用双指针的滑动窗口来实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
  public int lengthOfLongestSubstring(String s) {

    int left = 0, right = 0, sLen = s.length(), subMaxLen = 0;
    Set<Character> windows = new HashSet<>();
    while (right < sLen) {
      char c = s.charAt(right);
      right++;
      while (windows.contains(c)) {
        char c1 = s.charAt(left);
        left++;
        windows.remove(c1);
      }
      windows.add(c);
      subMaxLen = Math.max(subMaxLen, right - left);
    }
    return subMaxLen;
  }
}

时间复杂度

最差的情况是left扫了一遍s，right扫了一遍s，那就是2*s，去除常数最终的时间复杂度是O(N)

空间复杂度

额外空间left、right和两个数组，left和right的空间复杂度是O(1)可以不计，因为哈希集合是存放不同字符的，题目规定s 由英文字母、数字、符号和空格组成，所以字符集最大也就128，去除常数的空间复杂度为O(1)