- 关键字:最长不重复子串、双指针
- 难度:Medium
- 题目大意:求一个字符串最长不重复子串的长度
题目:
Given a string, find the length of the longest substring without repeating characters.
Example 1:
Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Example 2:
Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3:
Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Note that the answer must be a substring, "pwke" is a subsequence and not a substring.
思路:
使用两个指针l、r分别记录不重复子串的起始和终止位置,l、r初始值为0,使用set来放当前不重复的字符,r向右移动:
- 字符不重复时,直接将字符add到set,r继续向右移动;
- 字符重复时,l向右移动,同时set删除掉字符串l位置的字符;
- 重复上述步骤;
思路实现:
class Solution {
public int lengthOfLongestSubstring(String s) {
if(s.length()==0||s==null) return 0;
int maxLen = 1;
int l = 0;
int r = 1;
Set<Character> set = new HashSet<>();
set.add(s.charAt(l));
while(l<s.length()&&r<s.length()) {
if(!set.contains(s.charAt(r))) {
set.add(s.charAt(r));
maxLen = Math.max(maxLen, r-l+1);
r++;
}
else {
set.remove(s.charAt(l));
l++;
}
}
return maxLen;
}
}