后端 longest substring without repeating characters

anxing7 · May 20, 2020 · 17 hits

Problem

Given a string, find the length of the longest substring without repeating characters.

Example

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.


Thinking

Two pointers 处理,O(N)。


Answer

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class  {

public int lengthOfLongestSubstring(String s) {

if (s.length() == 0) return 0;

int maxLen = 1;
int n = s.length();
int ptr1 = 0, ptr2 = 1;

while (ptr2 < n){
int len = ptr2 - ptr1 + 1;
int index = s.substring(ptr1, ptr2).indexOf(s.charAt(ptr2));

if (index >= 0){
ptr1 += (index+1);
}
else{
if (len > maxLen)
maxLen = len;
}

ptr2++;
}

return maxLen;

}

}
No Reply at the moment.
You need to Sign in before reply, if you don't have an account, please Sign up first.