首页 > 代码库 > 3. Longest Substring Without Repeating Characters
3. Longest Substring Without Repeating Characters
Given a string, find the length of the longest substring without repeating characters.
Examples:
Given "abcabcbb"
, the answer is "abc"
, which the length is 3.
Given "bbbbb"
, the answer is "b"
, with the length of 1.
Given "pwwkew"
, 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.
public class Solution {
public int lengthOfLongestSubstring(String s) {
if (s.length() == 0) {
return 0;
}
Map<Character, Integer> ht = new HashMap<>();
int count = 0;
int max = 0;
int start = 0;
int end = 0;
while (end < s.length()) {
while (end < s.length() && !ht.containsKey(s.charAt(end))) {
ht.put(s.charAt(end), end);
end++;
count++;
}
max = Math.max(max, count);
if (end >= s.length()) {
break;
}
int mid = ht.get(s.charAt(end));
for (int i = start; i <=mid; i++) {
ht.remove(s.charAt(i));
}
start = mid + 1;
ht.put(s.charAt(end), end);
count = ht.size();
end++;
}
return Math.max(max, count);
}
}
3. Longest Substring Without Repeating Characters