forked from xiaoningning/java-algorithm-2010
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathLongestStringWithoutRepeat.java
More file actions
48 lines (41 loc) · 1.45 KB
/
LongestStringWithoutRepeat.java
File metadata and controls
48 lines (41 loc) · 1.45 KB
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/**
* Given a string, find the length of the longest substring without repeating characters.
* For example, the longest substring without repeating letters for "abcabcbb" is "abc",
* which the length is 3.
* For "bbbbb" the longest substring is "b", with the length of 1.
*/
public class LongestStringWithoutRepeat {
public static void main(String[] args) {
String s1 = "abcabcdbb";
System.out.println(longestStringWithoutRepeat(s1));
String s2 = "bbb";
System.out.println(longestStringWithoutRepeat(s2));
}
public static String longestStringWithoutRepeat(String s) {
boolean[] exist = new boolean[256]; //256 ASCII
int start = 0, j = 0, maxStart = 0, maxLen = 0, n = s.length();
while (j < n) {
if (exist[s.charAt(j)]) {
if (j - start > maxLen) {
maxLen = j - start;
maxStart = start;
}
while (s.charAt(start) != s.charAt(j)) {
exist[s.charAt(start)] = false;
start++;
}
j++;
start++;
} else {
exist[s.charAt(j)] = true;
j++;
}
}
// the last case a[n-1] is not repeated
if (n - start > maxLen) {
maxLen = n - start;
maxStart = start;
}
return s.substring(maxStart, maxStart + maxLen);
}
}