找出字符串中不含重复字符的最长子串的长度
1. 题目
给定一个字符串,找出其中不含重复字符的最长子串的长度。
示例1:
输入:"abcabcbb"
输出:3
解释:因为无重复字符的最长子串是:"abc",所以其长度为3
示例2:
输入:"bbbbb"
输出:1
解释:因为无重复字符的最长子串是:"b",所以其长度为1
示例3:
输入:"pwwkew"
输出:3
解释:因为无重复字符的最长子串是:"wke"或"kew",所以其长度为3
注意:必须是子串的长度,子串是连续的字符,中间不能跳跃字符,如"pwke"是一个子系列,不是子串。
2. 解题思路
2.1 思路一:滑动窗口
窗口通常是在数组/字符串中由开始和结束索引定义的一系列元素的集合,即[i, j)(左闭,右开)
,而滑动窗口是可以将两个边界向某一方向“滑动”的窗口。
例如:
我们将[i, j)
向右滑动1个元素,则它将变为[i+1, j+1)(左闭,右开)
用HashSet
存储当前处于窗口[i, j)(最初 j = i)
中的字符,然后我们向右滑动索引j
,如果它不在HashSet
中,我们会继续滑动j
,直到s[j]
已经存在于HashSet
中,此时没有重复的最长子字符串将会以索引i
开头
用
滑动窗口1.pngHashSet
存放当前处于滑动窗口中的字符,初始HashSet为空。
窗口的左边i
不动,右边j
向右滑动,依次遍历字符:j
为指向字符的索引。
当j = 0时,遍历字符p,加入HashSet -- [p],则目前无重复字符的最大子串长度maxSubLength = 1
当j = 1时,遍历字符w,加入HashSet -- [p, w],则maxSubLength = 2当j = 2时,遍历字符w,此时HashSet中已包含重复字符w,
滑动窗口2.png
则窗口的左边i
向右滑,右边j
不动,HashSet依次删除索引i
所指向的字符,直到HashSet不再包含该字符w,
然后重新将遍历字符w加入HashSet中,启动窗口j
继续右滑。窗口的左边
滑动窗口3.pngi
不动,右边j
继续向右滑动,依次遍历字符:j
为指向字符的索引
当j = 3时,遍历字符k,加入HashSet -- [w k]
当j = 4时,遍历字符e,加入HashSet -- [w k e],则此时maxSubLength = 3
当j = 5时,遍历字符w,此时HashSet中已包含重复字符w,
滑动窗口4.png
则窗口的左边i向右滑,右边j不动,HashSet依次删除索引i所指向的字符,直到HashSet不再包含该字符w,
然后重新将遍历字符w加入HashSet中,启动窗口j右滑。
结束,则maxSubLength = 3
代码实现:
public static int lengthOfLongestSubstring(String s) {
if (s == null || "".equals(s)) {
return 0;
}
int n = s.length();
Set<Character> set = new HashSet<>();
int maxLength = 0;
int i = 0;
int j = 0;
while (i < n && j < n) {
if (!set.contains(s.charAt(j))) {
set.add(s.charAt(j++));
maxLength = Math.max(j - i, maxLength);
} else {
set.remove(s.charAt(i++));
}
}
return maxLength;
}
2.2 思路二:优化的滑动窗口
针对上述的滑动窗口方法,不使用集合来判断一个字符是否存在,而定义字符到索引的映射map。
当找到重复字符时,可以立即跳过该窗口。
如果在[i, j)
范围内有与s[j]
重复的字符,索引为j'
,即[i, ... j', ... j)
,
我们不需要逐渐增加i
,可以直接跳过[i, j']
范围内的所有元素,并将i
变为j' + 1
举例:
s = "pwwkew"
,当 j = 2时,窗口[0, 2)
范围内有与s[2]
重复的字符w
,索引为1(j' = 1
),我们可以直接跳过[0, 1]
范围内的所有元素,将i
变为2(j' + 1
)
代码实现:
public static int lengthOfLongestSubstring(String s) {
if (s == null || "".equals(s)) {
return 0;
}
int n = s.length();
Map<Character, Integer> map = new HashMap<>(16);
int maxLength = 0;
for (int i = 0,j = 0; j < n; j++) {
if (map.containsKey(s.charAt(j))) {
i = Math.max(map.get(s.charAt(j)), i);
}
maxLength = Math.max(maxLength, j - i + 1);
map.put(s.charAt(j), j + 1);
}
return maxLength;
}
2.3 思路三:使用列表List存储不重复字符
依次遍历字符串 s 中的每次字符,若不是重复字符,加入一个列表list
中,若是重复字符,则删除列表list
中该重复字符以及前面的所有字符,然后再将该重复字符加入此列表list
中。
在遍历的过程中统计出列表list
中存储的最大字符个数,即为字符串 s 中不含重复字符的最长子串的长度。
代码实现
public static int lengthOfLongestSubstring(String s) {
if (s == null || "".equals(s)) {
return 0;
}
List<Character> list = new ArrayList<>();
int n = s.length();
int maxLength = 0;
for (int i = 0; i < n; i++) {
int index = list.indexOf(s.charAt(i));
if (index == -1) {
list.add(s.charAt(i));
maxLength = Math.max(list.size(), maxLength);
} else {
for (int j = index; j >= 0; j--) {
list.remove(j);
}
list.add(s.charAt(i));
}
}
return maxLength;
}