分组循环

题目	难度
2943. 最大化网格图中正方形空洞的面积	中等
2948. 交换得到字典序最小的数组	中等
2953. 统计完全子字符串	中等
2957. 消除相邻近似相等字符	中等
2982. 找出出现至少三次的最长特殊子字符串 II	中等

模板

    int n = s.length;
    int ans = 0, i = 0;
    while (i < n) {
        // 分组循环
        int st = i;
        for (i++; i < n && Math.abs(s[i] - s[i - 1]) <= 2; i++) {
        }
        ans += ...;
    }

2943. 最大化网格图中正方形空洞的面积

组内间隔为 1。

import java.util.Arrays;

public class Solution2943 {
    public int maximizeSquareHoleArea(int n, int m, int[] hBars, int[] vBars) {
        int maxH = getMax(hBars);
        int maxV = getMax(vBars);
        int min = Math.min(maxH, maxV);
        return min * min;
    }

    private int getMax(int[] bars) {
        int n = bars.length;
        Arrays.sort(bars);
        int max = 0;
        int i = 0;
        while (i < n) {
            // 分组循环
            int st = i;
            for (i++; i < n && bars[i] - bars[i - 1] == 1; i++) {
            }
            max = Math.max(max, i - st + 1);
        }
        return max;
    }
}

2948. 交换得到字典序最小的数组

组内间隔小于等于 limit。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Solution2948 {
    // 时间复杂度 O(nlogn)
    public int[] lexicographicallySmallestArray(int[] nums, int limit) {
        int n = nums.length;
        Integer[] ids = new Integer[n];
        for (int i = 0; i < n; i++) ids[i] = i;
        Arrays.sort(ids, Comparator.comparingInt(o -> nums[o]));

        int[] ans = new int[n];
        int i = 0;
        while (i < n) {
            // 分组循环
            int st = i;
            for (i++; i < n && nums[ids[i]] - nums[ids[i - 1]] <= limit; i++) {
            }
            Integer[] subIds = Arrays.copyOfRange(ids, st, i);
            Arrays.sort(subIds);
            for (int j = 0; j < subIds.length; j++) {
                ans[subIds[j]] = nums[ids[st + j]];
            }
        }
        return ans;
    }
}

2953. 统计完全子字符串

组内 字母表中的位置相差 至多 为 2。

public class Solution2953 {
    private char[] s;
    private int k;

    public int countCompleteSubstrings(String word, int k) {
        this.s = word.toCharArray();
        this.k = k;

        int n = s.length;
        int ans = 0, i = 0;
        while (i < n) {
            // 分组循环
            int st = i;
            for (i++; i < n && Math.abs(s[i] - s[i - 1]) <= 2; i++) {
            }
            ans += getSubAns(st, i);
        }
        return ans;
    }

    private int getSubAns(int st, int end) {
        int len = end - st;
        int res = 0;
        for (int m = 1; m <= 26 && m * k <= len; m++) {
            int span = m * k;
            // 滑动窗口
            int[] cnt = new int[26];
            for (int i = 0; i < span; i++) {
                cnt[s[st + i] - 'a']++;
            }
            if (checkAllEqK(cnt)) res++;
            for (int i = span; i < len; i++) {
                cnt[s[st + i] - 'a']++;
                cnt[s[st + i - span] - 'a']--;
                if (checkAllEqK(cnt)) res++;
            }
        }
        return res;
    }

    private boolean checkAllEqK(int[] cnt) {
        for (int i = 0; i < 26; i++) {
            if (cnt[i] > 0 && cnt[i] != k) {
                return false;
            }
        }
        return true;
    }
}

2957. 消除相邻近似相等字符

组内 在字母表中是相邻的。

public class Solution2957 {
    public int removeAlmostEqualCharacters(String word) {
        int n = word.length();
        char[] s = word.toCharArray();
        int ans = 0;
        int i = 0;
        while (i < n) {
            // 分组循环
            int st = i;
            for (i++; i < n && Math.abs(s[i] - s[i - 1]) <= 1; i++) {
            }
            ans += (i - st) / 2;
        }
        return ans;
    }
}

2982. 找出出现至少三次的最长特殊子字符串 II

组内 字母是相同的。

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Solution2982 {
    public int maximumLength(String s) {
        int n = s.length();
        char[] cs = s.toCharArray();
        int[] cnt = new int[26];
        Map<Character, List<Integer>> mp = new HashMap<>();
        int i = 0;
        while (i < n) {
            int st = i;
            for (i++; i < n && cs[i] == cs[i - 1]; i++) {
            }
            mp.computeIfAbsent(cs[st], e -> new ArrayList<>()).add(i - st);
            cnt[cs[st] - 'a'] += i - st;
        }
        int ans = -1;
        for (Map.Entry<Character, List<Integer>> entry : mp.entrySet()) {
            List<Integer> list = entry.getValue();
            list.sort(Comparator.reverseOrder());
            if (cnt[entry.getKey() - 'a'] < 3) continue;

            // top1 三等分
            int res = list.get(0) - 2;
            ans = Math.max(ans, res);
            // top1 二等分 + top2
            if (list.size() >= 2) {
                res = Math.min(list.get(0) - 1, list.get(1));
                ans = Math.max(ans, res);
            }
            // top1 + top2 + top3
            if (list.size() >= 3) {
                res = list.get(2);
                ans = Math.max(ans, res);
            }
        }
        return ans;
    }
}

（全文完）