最长不重复子串 和 最小字串的解题思路 —— 字节必考系列

最小子串覆盖问题(困难)

https://leetcode.cn/problems/minimum-window-substring/

最长子串不重复问题(中等)

1. 解法思路

这两个题都是研究子串的问题，对于这类子串问题，我们一般是才用双指针的方式来循环分析。这两个指针构成了子串的窗口，指向了子串后，我们可以对子串数据进行解析建模，记录每个窗口下子串的特征数据。

因此，我们的解体思路就是，双指针和计算窗口特征。

子串的窗口特征

最长子串不重复问题：需要统计的特征如，子串的字符集合，子串数据，子串字符为key以及索引为value的Map数据。

最小子串覆盖问题：需要统计的特征如，覆盖字符串的字符数量，当前最小长度的覆盖串, 子串字符为key以及数量为value的Map数据。

2. 公共点

思路流程是相通的，通过双指针实现子串窗口，并对窗口串进行特征计算，每个题的特征模型是不一样的，这些特征都会用到窗口的移动逻辑中去。

3. 不同点

最长子串不重复问题：子串的字符集合，子串数据，子串字符为key以及索引为value的Map数据。

1. 子串的字符集合用来生成子串；
2. 子串数据用来保存最长子串数据，每个窗口下都来比较，并保留长的字符串；
3. Map数据来留存子串中索引所在的位置，用来定位窗口左指针的移动，右指针右移步长是1，左指针直接移动到重复字符所在位置，否则左指针不移动。

最小子串覆盖问题：覆盖字符串的字符数量，当前最小长度的覆盖串, 子串字符为key以及数量为value的Map数据。

1. count值统计窗口子串中存在的字符个数，当count值等于最大值时候，左指针向右移动1，若count小于最大值，则右指针向右移动1.

2. Map数据初始化小串，value都是0，统计窗口子串时候出现字符则进行+1操作，左索引右移，则进行-1操作。

4. 方法论

1. 在每个子串处理的算法题目解法中，窗口模式通过双指针实现，对窗口元数据进行特征建模；

2. 通过特征对窗口进行左移和右移。比较每个窗口的结果数据，保留最优解，并最终返回。