LC 3：无重复字符的最长子串

题目

题目链接

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

示例 1:

输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: s = “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

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

提示：

• 0 <= s.length <= 5 * 10^4
• s 由英文字母、数字、符号和空格组成

尝试

思路

使用滑动窗口算法。初始化左指针 left 为 -1，右指针 right 为 0，返回值 ans 为 0。向右滑动右指针，如果右指针所指的字符 c 在 (left, right] 中没有出现，则更新答案 ans = max(ans, right - left) 并将字符 c 标记为已出现过。如果 c 在 (left, right] 中出现过，则向右滑动左指针收缩窗口，直至左指针指向字符 c'，c' 满足 c' = c。

根据上述算法过程，需要初始化一个队列来保存 (left, right] 中所有字符的值和位置，同时需要一个集合来保存 (left, right] 中所有的字符值。

复杂度分析

• 时间复杂度: $\mathcal{O(n)}$。同一个元素至多被右指针和左指针各遍历一次。
• 空间复杂度: $O(n)$。队列和集合中至多保存 $n$ 个元素。

代码

 public class Solution3 {
    class Pair {  
        int idx;  
        char ch;  
  
        public Pair(int idx, char ch) {  
            this.idx = idx;  
            this.ch = ch;  
        }  
    }  
  
    public int lengthOfLongestSubstring(String s) {  
        // 滑动窗口  
        char[] chars = s.toCharArray();  
        Deque<Pair> deque = new ArrayDeque<>();  
        Set<Character> set = new HashSet<>();  
        int left = -1, right = 0;  
        int ans = 0;  
        while (right < chars.length) {  
            char c = chars[right];  
            if (set.contains(c)) {  
                while (deque.peekFirst().ch != c) {  
                    Pair pair = deque.removeFirst();  
                    set.remove(pair.ch);  
                }  
                Pair pair = deque.removeFirst();  
                set.remove(pair.ch);  
                left = pair.idx;  
            } else {  
                set.add(c);  
                deque.addLast(new Pair(right, c));  
                ans = Math.max(ans, right - left);  
                right++;  
            }  
        }  
        return ans;  
    }  
  
    public static void main(String[] args) {  
        Scanner scanner = new Scanner(System.in);  
        while (scanner.hasNextLine()) {  
            String s = scanner.nextLine();  
            System.out.println(new Solution3().lengthOfLongestSubstring(s));  
        }  
    }  
}

优化

参考 灵神题解 进行优化。原版的队列似乎没有必要，集合可以用数组进行替换提高执行效率。s 的取值可以被 ASCII 覆盖，数组大小设置为 128。

复杂度分析

• 时间复杂度: $\mathcal{O(n)}$。
• 空间复杂度: $O(\vert\Sigma\vert)$。$\vert\Sigma\vert$ 为字符集大小，本题中 $\vert\Sigma\vert \leq 128$。

优化版代码

public class Solution3 {  
    public int lengthOfLongestSubstring(String s) {  
        char[] chars = s.toCharArray();  
        boolean[] visited = new boolean[128];  
        int left = 0;  
        int ans = 0;  
        for (int right = 0; right < chars.length; right++) {  
            char c = chars[right];  
            while (visited[c]) {  
                visited[chars[left]] = false;  
                left++;  
            }  
            visited[c] = true;  
            ans = Math.max(ans, right - left + 1);  
        }  
        return ans;  
    }  
  
    public static void main(String[] args) {  
        Scanner scanner = new Scanner(System.in);  
        while (scanner.hasNextLine()) {  
            String s = scanner.nextLine();  
            System.out.println(new Solution3().lengthOfLongestSubstring(s));  
        }  
    }  
}