D.二分查找－二分答案－求最大——2982. 找出出现至少三次的最长特殊子字符串 II

题目链接：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; } }