无重复字符的最长子串


题目描述

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

示例 1:

输入: “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”,所以其长度为 3。

示例 2:

输入: “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”,所以其长度为 1。

示例 3:

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

队列实现

本题是计算最长的不重复子串,而子串肯定是连续的。我们肯定都能想到,要遍历下输入的字符串,那么遍历的过程中,我们需要做什么呢?既然是计算字串的长度,那么我们遍历的过程中就要将字串保存下来。同时,每次保存新的字符的时候,需要判断原有的子串中是否包含了这个字符,如果包含了,那么我们要从字串的第一个字符开始,一直删除字符,直到不存在即将要加入的字符,然后计算当前子串的长度,与之前计算的长度比较,取较大值。拿 abcdefce 举例,我们遍历到第二个c字符的时候,已有的不含有重复字符的子串是 abcdef ,当要把c加入到已有的子串的时候,需要将前面的 abc 删除,那么新的子串为 defc。由于子串有后进后出的特性,于是我们使用队列来保存子串。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int lengthOfLongestSubstring1(String s) {
int count = 0;
Queue<Character> queue = new LinkedList<>();
int length = s.length();
for (int i = 0; i < length; i++) {
char c = s.charAt(i);
while (queue.contains(c)) {
queue.poll();
}
queue.offer(c);
count = Math.max(queue.size(), count);
}
return count;
}

双指针实现

双指针实现的思路和队列的实现一致,只不过使用两个指针i和j来指向子串的两端,判断 s.substring(i, j) 中是否包含当前的字符,若包含,则移动左指针i++,否则移动右指针j++。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int lengthOfLongestSubstring(String s) {
if (s.length() <= 1) {
return s.length();
}

int maxLength = 0, i = 0, j = 1;
while (j < s.length()) {
if (!s.substring(i, j).contains(String.valueOf(s.charAt(j)))) {
maxLength = Math.max(maxLength, j - i + 1);
j++;
} else {
if (i < j) {
i++;
} else {
j++;
}
}
}
return maxLength;
}

来源

无重复字符的最长子串 | 力扣(LeetCode)
无重复字符的最长子串 | 题解(LeetCode)


文章标题:无重复字符的最长子串
文章作者:cylong
文章链接:http://www.cylong.com/blog/2019/11/26/longest-substring-without-repeating-characters/
有问题或者建议欢迎在下方评论。欢迎转载、引用,但希望标明出处,感激不尽(●’◡’●)