至多包含两个不同字符的最长子串

难度:

标签:

题目描述

代码结果

运行时间: 135 ms, 内存: 16.4 MB

/*
 * 思路：
 * 1. Java Stream API 并不特别适合解决滑动窗口问题，因为它们主要用于集合操作。
 * 2. 但是我们可以使用 stream 操作符对字符进行过滤和转换。
 * 3. 使用基本的循环和 map 来记录字符的位置，并维护窗口的左右边界。
 */
import java.util.HashMap;
import java.util.Map;
import java.util.Collections;
import java.util.stream.IntStream;
 
public class Solution {
    public int lengthOfLongestSubstringTwoDistinct(String s) {
        if (s.length() < 3) return s.length();
 
        Map<Character, Integer> hashmap = new HashMap<>();
        int[] max_len = {2};
 
        IntStream.range(0, s.length()).forEach(right -> {
            hashmap.put(s.charAt(right), right);
 
            if (hashmap.size() == 3) {
                int del_idx = Collections.min(hashmap.values());
                hashmap.remove(s.charAt(del_idx));
                left = del_idx + 1;
            }
 
            max_len[0] = Math.max(max_len[0], right - left + 1);
        });
 
        return max_len[0];
    }
 
    private int left = 0;
}

解释

方法:

该题解使用滑动窗口的思路来解决问题。通过维护两个指针 x0 和 x1 分别记录窗口内最多两个不同字符的位置，同时用 y0 和 y1 记录对应的字符。每次遇到一个新字符时，根据情况更新 x0, x1, y0, y1 以及窗口的起始位置 srt，并更新最大长度 mx。最终返回 mx 即为所求的最长子串长度。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆

在这个算法中，如何确保在更新字符位置 x0 和 x1 时，始终保留窗口内最后出现的两个不同字符？

▷

在算法中，每次循环都会检查当前字符 v 是否等于 y0 或 y1。如果等于其中之一，例如 y0，则更新 x0 的位置为当前字符的索引，表示 y0 字符的最新位置。如果 v 不是 y0 或 y1，这意味着出现了一个新的字符，这时会判断 x0 和 x1 的大小（哪个更小，即哪个字符最早出现），并将较早的那个字符（x1）替换为新字符 v，同时更新 x0 和 y0 为当前字符的位置和值。这样，x0 和 x1 始终保留了窗口中最后出现的两个不同字符的位置。

🦆

当出现新字符而需要更新窗口时，为什么选择将窗口起始位置 srt 设置为 x0 而不是 x1？

▷

当出现一个新的字符需要更新窗口时，通过设置 srt 为 x0 的原因是在此之前 x0 位置的字符 y0 将不再是窗口中的有效字符，而将被新字符替换。因此，窗口的新起始位置应该是 x0 之后（即 x0 的位置），这是为了确保窗口内只有最多两个不同的字符。如果设置为 x1，则可能会包括被替换的旧字符，导致窗口内包含三个不同的字符。

🦆

算法中的变量 y0 和 y1 分别用来做什么？它们是如何与 x0 和 x1 互动的？

▷

在算法中，y0 和 y1 用来存储当前窗口中的两个不同字符。x0 和 x1 是这两个字符最后一次出现在字符串中的位置索引。每次碰到字符串中的字符 v 时，算法会检查 v 是否与 y0 或 y1 相等。如果相等，就更新相应的位置索引 x0 或 x1。如果 v 与 y0 和 y1 都不相同，表明遇到了一个新字符，这时候会更新其中一个旧字符的位置和值（基于 x0 和 x1 的比较），以保证窗口中只有两种字符。

🦆

在滑动窗口策略中，如果遇到的字符序列中只有一个种类的字符，这种情况下 srt, x0, x1 的值将如何变化？

▷

如果遇到的字符序列中只有一种字符，例如全部都是字符 'a'，那么每次遇到这个字符时，算法会检测到 v 是 y0 或 y1 中的一个（取决于初始或中间某状态下的赋值），并相应更新 x0 或 x1。由于没有第二种字符，x1 的值可能始终保持初始值。窗口起始位置 srt 在遇到第一个字符时被设置，后续不再改变，因为没有新的字符类型加入。因此，srt 将保持为初始索引 0，x0 或 x1 会更新为当前字符的最新位置，另一个保持不变。

相关问题

无重复字符的最长子串

给定一个字符串 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⁴
s 由英文字母、数字、符号和空格组成

滑动窗口最大值

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

示例 1：

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

示例 2：

输入：nums = [1], k = 1
输出：[1]

提示：

1 <= nums.length <= 10⁵
-10⁴ <= nums[i] <= 10⁴
1 <= k <= nums.length

至多包含 K 个不同字符的最长子串

K 个不同整数的子数组

给定一个正整数数组 nums和一个整数 k，返回 nums 中「好子数组」 的数目。

如果 nums 的某个子数组中不同整数的个数恰好为 k，则称 nums 的这个连续、不一定不同的子数组为「好子数组」。

例如，[1,2,3,1,2] 中有 3 个不同的整数：1，2，以及 3。

子数组 是数组的连续部分。

示例 1：

输入：nums = [1,2,1,2,3], k = 2
输出：7
解释：恰好由 2 个不同整数组成的子数组：[1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2].

示例 2：

输入：nums = [1,2,1,3,4], k = 3
输出：3
解释：恰好由 3 个不同整数组成的子数组：[1,2,1,3], [2,1,3], [1,3,4].

提示：

1 <= nums.length <= 2 * 10⁴
1 <= nums[i], k <= nums.length

用 Read4 读取 N 个字符 II - 多次调用相交链表