LeetCode link

Intuition

  • Use two pointers begin and end to represent the range of the substring.
  • Use a set to save the characters that has appeared.
  • when the end meet a character which has appeared, the start to move the begin, until the begin is the character.

solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public int lengthOfLongestSubstring(String s) {
Set<Character> set = new HashSet<>();
int maxLength = 0;
for (int begin = 0, end = 0; end < s.length(); end++) {
char c = s.charAt(end);
if (!set.contains(c)) {
set.add(c);
maxLength = Math.max(maxLength, end - begin + 1);
continue;
}
while (s.charAt(begin) != c) {
begin++;
}
begin++;
maxLength = Math.max(maxLength, end - begin + 1);
}
return maxLength;
}
}

problem

WA

reason

Forget to delete the character in the set when moving the begin.


modification

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public int lengthOfLongestSubstring(String s) {
Set<Character> set = new HashSet<>();
int maxLength = 0;
for (int begin = 0, end = 0; end < s.length(); end++) {
char c = s.charAt(end);
if (!set.contains(c)) {
set.add(c);
maxLength = Math.max(maxLength, end - begin + 1);
continue;
}
while (s.charAt(begin) != c) {
set.remove(s.charAt(begin));
begin++;
}
begin++;
maxLength = Math.max(maxLength, end - begin + 1);
}
return maxLength;
}
}