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

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

示例 1:

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

示例 2:

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

示例 3:

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

提示：

• $0\le s.length\le 5\times {10}^4$
• s 由英文字母、数字、符号和空格组成

解法一(滑动窗口)

思路分析

1. 首先确定是不含有重复字符子串而不是子序列;
2. 对于如何计算最长子串长度,可以采用滑动窗口算法,从左到右依次遍历整个字符串;
3. 使用变量left来表示最长子串的左边界(包含left指向的字符), 当指针i遍历到某个字符s[i]时;
4. 若s[i]出现过,即在区间[left, i-1]中有重复字符, 则需要得到重复字符在无重复字符子串中的位置,假设为j;
5. 则新得到的无重复子串区间为[j+1, i], 此时新的子串长度为i - (j+1) + 1, 即更新左边界left = j+1;
6. 在遍历整个字符串的过程中, 会出现很多个新的子串长度, 即最大的子串长度也在其中;
7. 同时在查找区间中是否有字符s[i]的重复字符时,可以采用哈希数据结构来降低查找的时间复杂度;

实现代码

class Solution {
	// 滑动窗口
    public int lengthOfLongestSubstring(String s) {
		int n = s.length();
		int ans = 0;
		// 无重复字符串 左边界
		int left = 0;
		// 哈希表 记录对应字符所处位置索引
		int[] hash = new int[129];
		for (int i = 0; i < 129; i++) {
			hash[i] = -1;
		}
		for (int i = 0; i < n; ++ i) {
			// 获取当前字符
			int ch = s.charAt(i);
			// 保证窗口的左边界只会向右变化
			left = Math.max(left, hash[ch]+1);
			// 与新的子串长度进行比较, 筛选出最长子串
			ans = Math.max(ans, i - start + 1);
			// 更新字符的所处位置
			hash[ch] = i;
		}
		return ans;
    }
}

复杂度分析

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$