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

1. 题目

给定一个字符串 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 由英文字母、数字、符号和空格组成

2. 思路

Tips: 整体思路很像209. 长度最小的子数组

  • 初始化哈希表map，该哈希表用于存储对应字符在滑动窗口范围内出现的次数
  • 初始化左指针i与右指针j位于0号下标，与结果变量result
  • 遍历字符串s，每次进入循环时，需要将j指针对应的字符计数增加1
  • 因为滑动窗口范围内会保证所有字符只出现1次，因此当该j指针对应的字符计数为1时，记录最新的result值，result值为实时的滑动窗口范围j - i + 1
  • 如果该j指针对应的字符计数大于1时，开始移动i指针，并实时更新对应i指针的字符计数，直至j指针对应字符计数为1，保证滑动窗口范围内的所有字符都只出现1次
  • 每次遍历后，需要向右移动j指针，试图扩张滑动窗口范围

3. 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public int lengthOfLongestSubstring(String s) {
        var map = new HashMap<Character, Integer>();
        var i = 0;
        var j = 0;
        var result = 0;
        var arr = s.toCharArray();

        while (i < arr.length && j < arr.length) {
            var ch = arr[j];
            increaseCount(map, ch, 1);
            if (map.get(ch) == 1) {
                result = Math.max(result, j - i + 1);
            }
            while (i <= j && map.get(arr[j]) > 1) {
                increaseCount(map, arr[i], -1);
                i++;
            }
            j++;
        }

        return result;
    }

    private void increaseCount(Map<Character, Integer> map, char ch, int count) {
        var val = map.getOrDefault(ch, 0);
        map.put(ch, val + count);
    }
}

4. 复杂度

  • 时间复杂度: O(n)
  • 空间复杂度: O(n)

image-20230816101116578