ccsp/src/leetcode/p2892/Solution.java

package leetcode.p2892;

import java.util.ArrayList;
import java.util.List;

/**
 * @see <a href='https://leetcode.cn/problems/find-longest-special-substring-that-occurs-thrice-ii/description/'>2982. 找出出现至少三次的最长特殊子字符串 II</a>
 * @ProjectName: LeetCode
 * @FileName: Solution
 * @Author: 杨逸
 * @Data:2024/5/30 9:39
 * @Description:
 * 给你一个仅由小写英文字母组成的字符串 s 。
 *
 * 如果一个字符串仅由单一字符组成，那么它被称为 特殊 字符串。例如，字符串 "abc" 不是特殊字符串，而字符串 "ddd"、"zz" 和 "f" 是特殊字符串。
 *
 * 返回在 s 中出现 至少三次 的 最长特殊子字符串 的长度，如果不存在出现至少三次的特殊子字符串，则返回 -1 。
 *
 * 子字符串 是字符串中的一个连续 非空 字符序列。
 *
 *
 *
 * 示例 1：
 *
 * 输入：s = "aaaa"
 * 输出：2
 * 解释：出现三次的最长特殊子字符串是 "aa" ：子字符串 "aaaa"、"aaaa" 和 "aaaa"。
 * 可以证明最大长度是 2 。
 * 示例 2：
 *
 * 输入：s = "abcdef"
 * 输出：-1
 * 解释：不存在出现至少三次的特殊子字符串。因此返回 -1 。
 * 示例 3：
 *
 * 输入：s = "abcaba"
 * 输出：1
 * 解释：出现三次的最长特殊子字符串是 "a" ：子字符串 "abcaba"、"abcaba" 和 "abcaba"。
 * 可以证明最大长度是 1 。
 *
 *
 * 提示：
 *
 * 3 <= s.length <= 5 * 105
 * s 仅由小写英文字母组成。
 */
public class Solution {
    public int maximumLength(String s) {
        ArrayList<List<Integer>> list = new ArrayList<>(26);

        for (int i = 0; i < 26; i++) {
            list.add(new ArrayList<>());
        }
        //按重复字符分组,记录重复字符的长度
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            int count = 1;
            while (i<s.length()-1){
                if (s.charAt(i+1)==c){
                    count++;
                }else{
                    break;
                }
                i++;
            }
            List<Integer> integers = list.get(c - 'a');
            if (integers == null)integers = new ArrayList<>();
            integers.add(count);
        }

        int result = -1;

        //遍历分组，找出符合条件的最大值
        for (List<Integer> integers : list) {
            if (integers.size()==0)continue;
           integers.sort((a, b) -> b - a);
           if (integers.size()==1){
               Integer integer = integers.get(0);
               if (integer >=3 && result < integer - 2) {
                   result = integer -2;
               }
           }else if (integers.size()==2){
               Integer v1 = integers.get(0);
               Integer v2 = integers.get(1);
               if (v1.equals(v2) && result < v1 - 1 && v1-1 != 0)result = v1 - 1;
               //差值为1的情况
               if (v1-v2==1){
                   if (result < v2)result = v2;
               }else {
                   if (v1>2 && result < v1 - 2)result = v1 - 2;
               }
           }else{
               Integer v1 = integers.get(0);
               Integer v2 = integers.get(1);
               Integer v3 = integers.get(2);
               //前三个重复字符长度相等
               if (v1.equals(v3) && result < v1)result = v1;
               if (!v1.equals(v3)){
                   if (v1.equals(v2)){
                       if (result < v1 - 1 && v1-1 != 0)result = v1-1;
                   }else if (v1-v2==1){
                       //差值为1的情况
                       if (result < v2)result = v2;
                   }else if (v1>2 && result < v1 - 2){
                       result = v1 - 2;
                   }
               }
           }
        }
        return result;
    }
}