题目链接：2982. 找出出现至少三次的最长特殊子字符串 II（中等）
算法原理：
解法：二分查找
98ms击败51.14%
时间复杂度O(Nlogn)
核心思路，我们可以通过顺序表数组，把各个字母的各个连续段长度存起来，通过二分查找找到符合的子串长度
①目标变量：子串长度
②目标条件：s中出现≥3次的最长特殊子字符串长度
③转换逻辑：当前子串长度mid下，能否有≥3次的最长特殊子字符串
具体步骤：
①确定区间边界：
left：0
right：s的长度
②确定二分模型：由于要找最长的特殊子串长度，找最长用最右端点模型，如果当前mid长度下不能凑出≥3次的最长特殊子字符串长度，说明mid太大了，应该向左调整，变小点以便适应更多次数，也就是说呈负相关单调：子串长度↑ 目标条件符合度↓
③check方法设计：
1.如果mid为0，说明一定为不能凑出特殊子串，直接返回false
2.遍历每个小写字母，看看每段的长度能否凑出来
遍历过程中如果遇到空表，直接跳过
如果这段比mid小，就跳过找下一段
比mid大就累加这段的贡献量，由于特殊子串连续，贡献量长度+1-mid
比如mid=3，该段=5，那么这段可以是123、234、345共3段，正好是5+1-3=3，对的上
如果凑不出就返回true，向左调整mid
Java代码：
class Solution { private static List<Integer>[] groups; public int maximumLength(String ss) { //统计每个字符的连续长度 char[] s=ss.toCharArray(); groups=new ArrayList[26]; Arrays.setAll(groups,_->new ArrayList<>()); int count=0; for(int i=0;i<s.length;i++){ count++; if(i+1==s.length||s[i]!=s[i+1]){ //把这一段的长度添加进去 groups[s[i]-'a'].add(count); //重新计数 count=0; } } //二分框架 int left=0,right=s.length; while(left<right){ int mid=left+(right-left+1)/2; if(check(mid)) right=mid-1; else left=mid; } //如果所有都不能凑出就返回-1 return check(left)?-1:left; } //判断能否存在某个字符，能凑出至少3个长度为mid的相同子串 //若不能凑出，则返回true向左调整mid private boolean check(int mid){ if(mid==0) return true; //遍历每个小写字母，看看每段的长度能否凑出来 for(List<Integer> word:groups){ //该字符无连续段，直接跳过 if(word.isEmpty()) continue; //统计该字符当前段能凑出mid长度子串的总数 int sum=0; for(int l:word){ if(l<mid) continue; sum+=l+1-mid;//累加该段的贡献量 if(sum>=3) return false; } } return true; } }
