lcpBi112

2839. 判断通过操作能否让字符串相等 I

方法一：模拟

class Solution {
    public boolean canBeEqual(String s1, String s2) {
        if (s1.equals(s2))
            return true;
        boolean[] flag = new boolean[4];
        int cnt = 0;
        for (int i = 0; i < 4; ++i) {
            char ch1 = s1.charAt(i), ch2 = s2.charAt(i);
            if (flag[i]) {
                continue;
            }
            if (ch1 == ch2) {
                flag[i] = true;
                ++cnt;
                continue;
            }
            if ((i == 0 || i == 1) && s1.charAt(i + 2) == ch2 && s2.charAt(i + 2) == ch1) {
                flag[i] = true;
                flag[i + 2] = true;
                cnt += 2;
            }
        }
        return cnt == 4;
    }
}

2840. 判断通过操作能否让字符串相等 II

方法一：计数

class Solution {
    public boolean checkStrings(String s1, String s2) {
        int n = s1.length();
        int[] cntEven = new int[26], cntOdd = new int[26];
        for (int i = 0; i < n; ++i) {
            char ch1 = s1.charAt(i), ch2 = s2.charAt(i);
            if (i % 2 == 0) {
                ++cntEven[ch1 - 'a'];
                --cntEven[ch2 - 'a'];
            }
            else {
                ++cntOdd[ch1 - 'a'];
                --cntOdd[ch2 - 'a'];
            }
        }
        for (int i = 0; i < 26; ++i) {
            if (cntEven[i] != 0)
                return false;
            if (cntOdd[i] != 0)
                return false;
        }
        return true;
    }
}

2841. 几乎唯一子数组的最大和

方法一：滑动窗口

class Solution {
    public long maxSum(List<Integer> nums, int m, int k) {
        long res = 0, s = 0;
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int i = 0; i < nums.size(); ++i) {
            int x = nums.get(i);
            s += x;
            cnt.put(x, cnt.getOrDefault(x, 0) + 1);
            if (i >= k - 1) {
                if (cnt.size() >= m)
                    res = Math.max(res, s);
                int y = nums.get(i - k + 1);
                s -= y;
                cnt.put(y, cnt.get(y) - 1);
                if (cnt.get(y) == 0)
                    cnt.remove(y);
            }
        }
        return res;
    }
}

2842. 统计一个字符串的 k 子序列美丽值最大的数目

方法一：组合数学 + 快速幂

class Solution {
    int MOD = (int) 1e9 + 7;
    public int countKSubsequencesWithMaxBeauty(String s, int k) {
        int n = s.length();
        int[] cnt = new int[26];
        for (int i = 0; i < n; ++i)
            cnt[s.charAt(i) - 'a']++;
        var cc = new TreeMap<Integer, Integer>();
        for (int c : cnt)
            if (c > 0)
                cc.put(c, cc.getOrDefault(c, 0) + 1);


        long res = 1;
        for (Map.Entry<Integer, Integer> entry : cc.descendingMap().entrySet()) {
            int num = entry.getKey(), count = entry.getValue();
            if (count >= k)
                return (int) ((res * comb(count, k) % MOD ) % MOD * pow(num, k) % MOD);
            res = res * pow(num, count) % MOD;
            k -= count;
        }
        return 0;
    }

    private long pow(long x, int n) {
        long res = 1;
        for (; n > 0; n /= 2) {
            if (n % 2 > 0)
                res = res * x % MOD;
            x = x * x % MOD;
        }
        return res;
    }

    // 适用于 n 和 k 都比较小的场景（本题至多 26）
    private long comb(long n, int k) {
        long res = n;
        for (int i = 2; i <= k; i++)
            res = res * --n / i; // n,n-1,n-2,... 中的前 i 个数至少有一个因子 i
        return res % MOD;
    }
}