3 Longest Substring Without Repeating Characters

# 1. Question

Given a string, find the length of thelongest substringwithout 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 asubstring,`"pwke"`is asubsequenceand not a substring.

# 2. Implementation

(1) Two Pointer + Hash
1
class Solution {
2
public int lengthOfLongestSubstring(String s) {
3
if (s == null || s.length() == 0) {
4
return 0;
5
}
6
7
int maxLen = 0;
8
int start = 0, end = 0;
9
int count = 0;
10
int[] map = new int;
11
12
while (end < s.length()) {
13
if (map[s.charAt(end)] > 0) {
14
++count;
15
}
16
++map[s.charAt(end)];
17
++end;
18
19
while (count > 0) {
20
if (map[s.charAt(start)] > 1) {
21
--count;
22
}
23
--map[s.charAt(start)];
24
++start;
25
}
26
maxLen = Math.max(maxLen, end - start);
27
}
28
return maxLen;
29
}
30
}
Copied!

# 3. Time & Space Complexity

Two Pointer + Hash: 时间复杂度O(n), 空间复杂度O(1)