首页 > itarticle > leetcode “3. longest substring without repeating characters”

leetcode “3. longest substring without repeating characters”

admin 11月 13, 2020 0

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

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

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