最长字串

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

难度中等7426收藏分享切换为英文接收动态反馈
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:
输入: s = “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
示例 2:
输入: s = “bbbbb” 输出: 1 解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。
示例 3:
输入: s = “pwwkew” 输出: 3 解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，”pwke” 是一个子序列，不是子串。

用一个set记录字符串是否存在+指针。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int p = 0,q=0;
        HashSet<Character> set = new HashSet();
        int max = 0;
        while(q<s.length()){
            char c = s.charAt(q);
            if(p!=q && set.contains(c)){
                char a = s.charAt(p);
                set.remove(a);
                p++;
            }else{
                set.add(c);
                q++;
                max = max>q-p?max:q-p;
            }
        }
        return max;
    }
}

记录上一次字符串出现的位置

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length(), ans = 0;
        Map<Character, Integer> map = new HashMap<>();
        for (int end = 0, start = 0; end < n; end++) {
            char alpha = s.charAt(end);
            if (map.containsKey(alpha)) {
                start = Math.max(map.get(alpha), start);
            }
            ans = Math.max(ans, end - start + 1);
            map.put(s.charAt(end), end + 1);
        }
        return ans;
    }
}