给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。
示例 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 由英文字母、数字、符号和空格组成
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
1、滑动窗口
考虑使用滑动窗口,需要两个指针截取子串,判断子串是否包含重复字符,若不包含重复字符,则将右指针右移,若右指针右移后指向的字符在子串中已经存在,则将左指针右移直到子串中再无重复字符。每次移动指针都需要判断是否存在重复字符,使用哈希集合进行判断。
class Solution {
public int lengthOfLongestSubstring(String s) {
Set<Character> set = new HashSet<>();
int length = s.length();
int maxLength = 0;
int left = 0;
int right = 0;
while(left < length && right < length){
if(set.contains(s.charAt(right))){
int curLength = set.size();
set = new HashSet<>();
maxLength = Math.max(curLength, maxLength);
while(s.charAt(left) != s.charAt(right)){
left++;
}
left = right + 1;
}
set.add(s.charAt(right++));
}
return maxLength;
}
}
不出意外解答错误,仅当字符串中存在重复字符时才进行最长子串的计算,则字符串中无重复字符时结果便为0。首先可以确定的是,右指针每次都会右移,则可改用for循环不停移动右指针,当遇到重复字符时,移动左指针,同时将对应字符从哈希集合中删除,则在哈希集合中便可始终维护当前的无重复字符子串。
class Solution {
public int lengthOfLongestSubstring(String s) {
Set<Character> set = new HashSet<>();
int length = s.length();
int maxLength = 0;
int left = 0;
for(int right = 0; right < length; right++){
if(set.contains(s.charAt(right))){
while(s.charAt(left) != s.charAt(right)){
set.remove(s.charAt(left));
left++;
}
left++;
}
set.add(s.charAt(right));
maxLength = Math.max(maxLength, (int)set.size());
}
return maxLength;
}
}
网友评论