LeetCode 003 无重复字符的最长子串

继续

问题

给定一个字符串，找出不含有重复字符的最长子串的长度。

示例：
给定 "abcabcbb" ，没有重复字符的最长子串是 "abc" ，那么长度就是3。
给定 "bbbbb" ，最长的子串就是 "b" ，长度是1。
给定 "pwwkew" ，最长子串是 "wke" ，长度是3。请注意答案必须是一个子串，"pwke" 是 子序列 而不是子串。

解答

滑动窗口：定义空集合，之后左边i先固定，右边j向右走，判断集合中是否存在j所对应的字符，若不存在，则添加，且j++，同时最长子串长度也更新；
若集合中已存在j所对应的字符，则集合移除左边i对应的字符，i++ 向右走一步。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        Set<Character> set = new HashSet<>();
        int maxLen = 0, i = 0, j = 0;
        while(i < n && j < n) {
            if(!set.contains(s.charAt(j))) {
                set.add(s.charAt(j++));
                maxLen = Math.max(maxLen, j - i);
            } else {
                set.remove(s.charAt(i++));
            }
        }
        return maxLen;
    }
}

复杂度分析：

• 时间复杂度：$O(n)$
• 空间复杂度：$O(min(m, n))$，需要$O(k)$的空间大小，k为集合的大小，同时集合的大小取决于字符串长度n和字符集的大小m。