目录
1.前言
2.题目解析
3.算法原理
4.代码实现
1.前言
首先我打算介绍一下，我对滑动窗口的理解。
滑动窗口可以分为四个步骤：
进窗口： 在这一步骤中，我们决定了要在窗口中维护的信息。例如，在这个问题中，我们需要维护字符种类的个数。只要字符种类个数不超过2个，窗口就是合法的，我们就可以继续向右移动窗口。
判断： 在进入窗口后，我们需要检查窗口是否变得非法。如果窗口不再合法，我们就需要执行出窗口的操作。
出窗口： 出窗口的过程是从一个非法窗口恢复到合法窗口的过程。我们通过移动左边界指针来实现这一点。
更新结果： 在每个合法窗口中，我们可能需要更新问题的最优解。这可能会发生在进窗口、判断或出窗口的任何阶段。
滑动窗口算法的核心思想是使用两个同向指针（通常是左右指针）来定义一个窗口，并根据问题的要求移动窗口的位置，以达到解决问题的目的。这种算法通常能够有效地减少重复计算，并在线性时间内解决许多问题。
2.题目解析
包含不超过两种字符的最长子串_牛客题霸_牛客网
窗口中的元素不大于2为合法窗口，求最长的合法窗口。
3.算法原理
使用滑动窗口： 采用滑动窗口算法来解决问题。通过维护一个窗口，窗口内的字符种类个数不超过两个，来找到满足条件的最长子串。
初始化窗口和变量： 定义两个指针
left和right，分别指向窗口的左右边界。初始化一个大小为 26 的整型数组hash，用于记录窗口内每种字符出现的次数。另外，定义一个变量flag用于记录窗口内不同字符的个数，初始值为 0；定义一个变量max用于记录最长子串的长度，初始值为 -1。移动右指针： 右指针向右移动，进入窗口。每次移动右指针，更新窗口内字符的出现次数，并根据情况更新
flag的值。判断窗口合法性： 判断窗口是否合法，即窗口内不同字符的个数是否超过两个。如果超过两个，需要移动左指针缩小窗口，直到窗口重新合法。
更新最长子串长度： 在每次窗口合法的情况下，更新
max的值，记录当前最长子串的长度。返回结果： 循环结束后，返回
max，即最终的结果，即最长子串的长度。
4.代码实现
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
while (in.hasNext()) { // 注意 while 处理多个 case
String str = in.next();
//1.通过hash表 + flag变量，来判断窗口是否合法
int[] hash = new int[26];
int flag = 0, max = -1;
int left = 0,right = 0;
char[] chs = str.toCharArray();
int n = chs.length;
while(right < n){
//2.进窗口
if (hash[chs[right] - 'a'] == 0){
flag++;
}
hash[chs[right] - 'a']++;
right++;
while(flag > 2){//违法窗口
//3.出窗口
hash[chs[left] - 'a']--;
if (hash[chs[left] - 'a'] == 0){
flag--;
}
left++;
}
//4.更新结果
max = Math.max(max,right - left);
}
System.out.println(max);
}
}
}
