forked from rpj911/LeetCode_algorithm
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathLengthOfLongestSubstring.java
More file actions
95 lines (71 loc) · 2.34 KB
/
LengthOfLongestSubstring.java
File metadata and controls
95 lines (71 loc) · 2.34 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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
package Algorithms.string;
import java.util.HashMap;
public class LengthOfLongestSubstring {
public int lengthOfLongestSubstring(String s) {
if (s == null) {
return 0;
}
int len = s.length();
// The start of the window.
int start = 0;
int max = 0;
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
for (int end = 0; end < len; end++) {
char c = s.charAt(end);
if (map.containsKey(c)) {
if (map.get(c) >= start) {
start = map.get(c) + 1;
}
}
map.put(c, end);
int subLen = end - start + 1;
max = Math.max(max, subLen);
}
return max;
}
public int lengthOfLongestSubstring1(String s) {
if (s == null) {
return 0;
}
int max = 0;
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
int len = s.length();
int l = 0;
for (int r = 0; r < len; r++) {
char c = s.charAt(r);
if (map.containsKey(c) && map.get(c) >= l) {
l = map.get(c) + 1;
}
// replace the last index of the character c.
map.put(c, r);
// replace the max value.
max = Math.max(max, r - l + 1);
}
return max;
}
// SOLUTION 2: use the array.
public int lengthOfLongestSubstring2(String s) {
if (s == null) {
return 0;
}
int max = 0;
// suppose there are only ASCII code.
int[] lastIndex = new int[128];
for (int i = 0; i < 128; i++) {
lastIndex[i] = -1;
}
int len = s.length();
int l = 0;
for (int r = 0; r < len; r++) {
char c = s.charAt(r);
if (lastIndex[c] >= l) {
l = lastIndex[c] + 1;
}
// replace the last index of the character c.
lastIndex[c] = r;
// replace the max value.
max = Math.max(max, r - l + 1);
}
return max;
}
}