本题和LC 395.Longest-Substring-with-At-Least-K-Repeating-Characters
的风格非常类似。传统的双指针非常难做,无法设计能让左右指针都单向移动的策略。而二分搜值也没有单调性的依据(并不是滑窗长度越长越容易满足条件)。
本题的滑窗法的关键设计,在于要保证“滑窗内不同字符的种类数目固定为k”。k是可以从1到26遍历一遍。当固定某个k时,我们一旦逐个遍历左指针i,相应地一定能找到一个最远的右指针j,使得[i:j]里面的字符种类是k,然后只需要检查这个滑窗里面每个字符是否都存在大小写两个版本即可。然后我们左指针i右移一位,那么右指针j也一定只需要相应地单调右移即可,以继续满足“字符种类恰为k”的要求。可以,我们用线性的时间就可以遍历所有这样的滑窗,找到其中最长的、且合法的滑窗即可。
总的时间复杂度就是o(26N).