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;
    }
}