|
32 | 32 | */ |
33 | 33 | public class _3 { |
34 | 34 | /** |
35 | | - * Solution 1: Violence method |
| 35 | + * Slide window method of optimize |
36 | 36 | * |
37 | | - * @param s |
38 | | - * @return |
| 37 | + * @param s target string |
| 38 | + * @return size |
39 | 39 | */ |
40 | 40 | public int lengthOfLongestSubstring(String s) { |
41 | | - int n = s.length(); |
42 | | - int ans = 0; |
43 | | - for (int i = 0; i < n; i++) { |
44 | | - for (int j = i + 1; j <= n; j++) { |
45 | | - if (allUnique(s, i, j)) { |
46 | | - ans = Math.max(ans, j - i); |
47 | | - } |
48 | | - } |
49 | | - } |
50 | | - return ans; |
51 | | - } |
52 | | - |
53 | | - private boolean allUnique(String s, int start, int end) { |
54 | | - Set<Character> aSet = new HashSet<>(); |
55 | | - for (int i = start; i < end; i++) { |
56 | | - if (aSet.contains(s.charAt(i))) { |
57 | | - return false; |
58 | | - } else { |
59 | | - aSet.add(s.charAt(i)); |
60 | | - } |
61 | | - } |
62 | | - return true; |
63 | | - } |
64 | | - |
65 | | - /** |
66 | | - * Solution 2: Slide window method |
67 | | - * |
68 | | - * @param s |
69 | | - * @return |
70 | | - */ |
71 | | - public int lengthOfLongestSubstring2(String s) { |
72 | | - int n = s.length(); |
73 | | - Set<Character> set = new HashSet<>(); |
74 | | - int ans = 0, i = 0, j = 0; |
75 | | - while (i < n && j < n) { |
76 | | - // try to extend the range [i, j] |
77 | | - if (!set.contains(s.charAt(j))) { |
78 | | - set.add(s.charAt(j++)); |
79 | | - ans = Math.max(ans, j - i); |
80 | | - } else { |
81 | | - set.remove(s.charAt(i++)); |
82 | | - } |
83 | | - } |
84 | | - return ans; |
85 | | - } |
86 | | - |
87 | | - /** |
88 | | - * Solution 3: Slide window method of optimize |
89 | | - * |
90 | | - * @param s |
91 | | - * @return |
92 | | - */ |
93 | | - public int lengthOfLongestSubstring3(String s) { |
94 | | - int n = s.length(), ans = 0; |
| 41 | + int length = s.length(), ans = 0; |
95 | 42 | // current index of character |
96 | 43 | Map<Character, Integer> map = new HashMap<>(); |
97 | 44 | // try to extend the range [i, j] |
98 | | - for (int j = 0, i = 0; j < n; j++) { |
99 | | - if (map.containsKey(s.charAt(j))) { |
100 | | - i = Math.max(map.get(s.charAt(j)), i); |
| 45 | + for (int i = 0, j = 0; i < length; i++) { |
| 46 | + if (map.containsKey(s.charAt(i))) { |
| 47 | + j = Math.max(map.get(s.charAt(i)), j); |
101 | 48 | } |
102 | | - ans = Math.max(ans, j - i + 1); |
103 | | - map.put(s.charAt(j), j + 1); |
| 49 | + ans = Math.max(ans, i - j + 1); |
| 50 | + map.put(s.charAt(i), i + 1); |
104 | 51 | } |
105 | 52 | return ans; |
106 | 53 | } |
|
0 commit comments