3. 无重复字符的最长子串

3. 无重复字符的最长子串

暴力解法

将字符串的每个字符作为起点计算不重复的子串长度，最大值为答案

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Set<Character> set = new HashSet<>();
        int max = 0;
        for (int i = 0; i < s.length(); i++) {
            for (int j = i; j < s.length() && !set.contains(s.charAt(j)); j++) {
                set.add(s.charAt(j));
                max = Math.max(max, set.size());
            }
            set.clear();
        }
        return max;
    }
}

滑动窗口

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> map = new HashMap<>();
        int left = 0;
        int max = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            // 注意要用 Math.max 函数，解决 map.get(c)+1 比 left 小导致结果出错的情况
            if (map.containsKey(c)) {
                left = Math.max(left, map.get(c) + 1);
            }
            map.put(c, i);
            max = Math.max(i - left + 1, max);
        }
        return max;
    }
}