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

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

难度 中等

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

Given a string s, find the length of the longest substring without repeating characters.

示例 1:

输入: s = "abcabcbb"

输出: 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 由英文字母、数字、符号和空格组成

递推法

记录 以每个字符结尾的最长无重复子串 和 以每个字符结尾的最长无重复子串长度

对于字符串 pwwkew

0	1	2	3	4	5
p	w	w	k	e	w

位置	字符	以这个字符结尾的最长无重复子串	以这个字符结尾的最长无重复子串长度
0	p	p	1
1	w	pw	2
2	w	w	1
3	k	wk	2
4	e	wke	3
5	w	kew	3

• pi 是 s[i] 字符上一次出现的位置
• li 是以 s[i] 字符结尾的最长不重复子串的开始索引（最左索引）
• 用 i 遍历整个字符串

尝试让 li 向左侧延伸

• li 指向的字符 不能等于 当前 i 指向的字符，因此需要 记录 i 指向字符上一次出现的位置 pi

0			pi		li		i - 1	i
			D				A	D

上述情况：pi < li ，说明 [li, i - 1] 之间必然没有重复字符，以 s[i] 结尾的最长不重复子串为 [li, i]

0		Li	pi				i - 1	i
			D				A	D

上述情况： pi > li ， [li, i - 1] 是以 s[i - 1] 结尾的不重复子串。则，以 s[i] 结尾的最长不重复子串为 [pi + 1, i]

0			li pi				i - 1	i
			D				A	D

上述情况： pi = li ，则以 s[i] 结尾的最长不重复子串为 [pi + 1, i] 也等于 [li + 1, i]

综上，分为两种情况进行实现：

1. pi < li -> [li, i]
2. pi ≥ li -> [li + 1, i]

• 用 哈希表 存储某字符上一次出现的位置
• 每次对 s[i] 计算出最长不重复子串范围后，将子串开始位置存储到 li 中，然后 i++，对于下一个 s[i] 而言，li 存储的就是 [li, i - 1] 最长不重复子串的开始索引
• 每次 pi 从 HashMap 查询获得
  • 如果 pi 为 null，说明 s[i] 字符根本没出现过，那么最长不重复子序列就是 [li, i]，那么在程序实现上就要满足 pi < li 那么手动将 pi 设置的尽可能小 （尽可能靠数组的起始侧） 即可
  • hashMap.getOrDefault(chars[i], -1) ： 有值就取值，没值为 null 的话，用 -1 替换

public int lengthOfLongestSubstring(String s) {

if (s.length() == 0) return 0;

// pi 存放每一个字符上一次出现的位置

Map<Character, Integer> preIndexes = new HashMap<>();

char[] chars = s.toCharArray();

preIndexes.put(chars[0], 0);

int maxLen = 1;

int li = 0; // 最初的 i = 1 ， 那么最初的 i-1 就是 0

// 因为算法执行到 i 时，需要用 i - 1 和 li 之类的东西，所以应当从 1 开始遍历

for (int i = 1; i < chars.length; i++) {

// i 字符上一次出现的位置

int pi = preIndexes.getOrDefault(chars[i], -1);

if (pi >= li)

li = pi + 1; // 覆盖 li 的值

// 把本次字符出现的位置存储到 Map

preIndexes.put(chars[i], i);

maxLen = Math.max(i - li + 1, maxLen);

}

return maxLen;

}

滑动窗口法

• HashMap 记录每个字符最后一次出现的位置
• 假想一个滑动窗口，其中包含着最长不重复子串
  • left 为滑动窗口的最左侧位置
  • 用 i 遍历字符串，发现重复字符就调整 left 的值，把重复部分移出滑动窗口
• 取过程中滑动窗口长度的最大值：Max {i - left + 1}

public int lengthOfLongestSubstring(String s) {

if (s.length() < 2) return s.length();

// HashMap 存储每个字符最后出现的位置

int[] charPositions = new int[128]; // ASCII

for (int i = 0; i < charPositions.length; i++)

charPositions[i] = -1;

int max = 0; // 最长长度

int left = 0; // 窗口左侧指针

char[] chars = s.toCharArray();

for (int i = 0; i < chars.length; i++) {

if (charPositions[chars[i]] != -1)

left = Math.max(left, charPositions[chars[i]] + 1);

charPositions[chars[i]] = i;

max = Math.max(max, i - left + 1);

}

return max;

}