LeetCode Contest 378

100166. Check if Bitwise OR Has Trailing Zeros

给你一个 正整数 数组 nums 。

你需要检查是否可以从数组中选出 两个或更多 元素，满足这些元素的按位或运算（ OR）结果的二进制表示中 至少 存在一个尾随零。

例如，数字 5 的二进制表示是 "101"，不存在尾随零，而数字 4 的二进制表示是 "100"，存在两个尾随零。

如果可以选择两个或更多元素，其按位或运算结果存在尾随零，返回 true；否则，返回 false 。

测试样例：

输入：nums = [1,2,3,4,5]

输出：true

解释：如果选择元素 2 和 4，按位或运算结果是 6，二进制表示为 "110" ，存在一个尾随零。

解答：这道题目范围很小，直接按照题意双循环暴力运算。

class Solution {
    public boolean hasTrailingZeros(int[] nums) {
        for (int i = 0; i < nums.length; ++i) {
            for (int j = i + 1; j < nums.length; ++j) {
                int tmp = nums[i] | nums[j];
                if (tmp % 2 == 0) {
                    return true;
                }
            }
        }
        return false;
    }
}

100184. Find Longest Special Substring That Occurs Thrice II

给你一个仅由小写英文字母组成的字符串 s 。

如果一个字符串仅由单一字符组成，那么它被称为 特殊 字符串。例如，字符串 "abc" 不是特殊字符串，而字符串 "ddd"、"zz" 和 "f" 是特殊字符串。

返回在 s 中出现 至少三次 的 最长特殊子字符串 的长度，如果不存在出现至少三次的特殊子字符串，则返回 -1 。

子字符串 是字符串中的一个连续 非空 字符序列。

测试样例：

输入：s = "aaaa"

输出：2

解释：出现三次的最长特殊子字符串是 "aa" ：子字符串 "aaaa"、"aaaa" 和 "aaaa"。可以证明最大长度是 2 。

解答：第二题和第三题一样，我就只放一道题目的题解了。按照测试集合，我们知道字符串中，最长的连续自数组的长度 - 2必然是一个解。还有一种情况是类似aabaabaa，由于一个b隔断了，会导致aa还是最长字符串。为了解决这种情况，我们需要记录连续字符串的长度，并且排序。有一段逻辑会计算不同长度的结果。

class Solution {
    public int maximumLength(String s) {
        PriorityQueue<Integer>[] maxMem = new PriorityQueue[26];
        for (int i = 0; i < 26; ++i) {
            maxMem[i] = new PriorityQueue<>();
        }
        int last = -1, len = 0;
        for (int i = 0; i <= s.length(); ++i) {
            if (i == s.length() || s.charAt(i) != last) {
                if (last != -1) {
                    maxMem[last - 'a'].add(len);
                    if (maxMem[last - 'a'].size() > 3) {
                        maxMem[last - 'a'].poll();
                    }
                }
                if (i < s.length()) {
                    last = s.charAt(i);
                    len = 1;
                }
            } else {
                ++len;
            }
        }
        int res = -1;
        for (PriorityQueue<Integer> t : maxMem) {
            ArrayList<Integer> list = new ArrayList<>();
            while (!t.isEmpty()) {
                list.add(t.poll());
            }
            for (int i = 0; i < list.size(); ++i) {
                res = Math.max(res, list.get(i) - 2);
                if (list.size() > i + 2) {
                    res = Math.max(res, list.get(i));
                } else if (i + 1 < list.size()) {
                    res = Math.max(res, list.get(i) - 1);
                    if (list.get(i + 1) > list.get(i)) {
                        res = Math.max(res, list.get(i));
                    }
                }
            }
        }
        return res <= 0 ? -1 : res;
    }
}

100129. Palindrome Rearrangement Queries

给你一个长度为 偶数 n ，下标从 0 开始的字符串 s 。

同时给你一个下标从 0 开始的二维整数数组 queries ，其中 queries[i] = [ai, bi, ci, di] 。

对于每个查询 i ，你需要执行以下操作：

• 将下标在范围 0 <= ai <= bi < n / 2 内的 子字符串 s[ai:bi] 中的字符重新排列。
• 将下标在范围 n / 2 <= ci <= di < n 内的 子字符串 s[ci:di] 中的字符重新排列。

对于每个查询，你的任务是判断执行操作后能否让 s 变成一个 回文串 。

每个查询与其他查询都是 独立的 。

请你返回一个下标从 0 开始的数组 answer ，如果第 i 个查询执行操作后，可以将 s 变为一个回文串，那么 answer[i] = true，否则为 false 。

• 子字符串 指的是一个字符串中一段连续的字符序列。
• s[x:y] 表示 s 中从下标 x 到 y 且两个端点 都包含 的子字符串。

测试样例：

输入：s = "abcabc", queries = [[1,1,3,5],[0,2,5,5]]

输出：[true,true]

解释：- a0 = 1, b0 = 1, c0 = 3, d0 = 5

• 你可以重新排列 s[1:1] => abcabc 和 s[3:5] => abcabc 。
• 为了让 s 变为回文串，s[3:5] 可以重新排列得到 => abccba 。
• 现在 s 是一个回文串。所以 answer[0] = true 。

第二个查询：

• a1 = 0, b1 = 2, c1 = 5, d1 = 5.
• 你可以重新排列 s[0:2] => abcabc 和 s[5:5] => abcabc 。
• 为了让 s 变为回文串，s[0:2] 可以重新排列得到 => cbaabc 。
• 现在 s 是一个回文串，所以 answer[1] = true 。

解答：这道题目，难在编程上。需要很细心（多WA几次，就知道需要考虑的场景了。。。）。因为这个条件0 <= ai <= bi < n / 2，n / 2 <= ci <= di < n。我们可以知道，query的区间必然不重叠。又因为我们需要知道字符串是否可以变成回文，所以我们需要把ci和di映射回去，变成mci和mdi。映射关系为 mp = len - 1 - p。

• 如果映射回去的区间和原来a, b完全没有重叠，或者是一个字区间的关系，这种情况还是比较简单的，我们只要比较不能变动的范围内是否是回文字符串，同时可以变动的区间，字母数前缀和一致。
• 否则，我们需要判断重叠区间的长度，并且判断a,b和mc,md的超级区间是否前缀和一致。最后非重叠部分的字符，也能出现在区间内。

class Solution {
    public class RollingHash61 {
        static final long mod = (1L << 61) - 1;
        public long M;
        public long[] pows;
        public long[] hs;
        public int hp;

        public RollingHash61(long M, int n) {
            assert M > 0;
            assert n > 0;
            this.M = M;
            this.pows = makePows(M, n);
            this.hs = new long[n + 1];
            this.hp = 0;
        }

        public long mul(long a, long b) {
            long al = a & (1L << 31) - 1, ah = a >>> 31;
            long bl = b & (1L << 31) - 1, bh = b >>> 31;
            long low = al * bl;
            long mid = al * bh + bl * ah;
            long high = ah * bh + (mid >>> 31);
            long ret = mod(mod(2 * high + low) + ((mid & (1L << 31) - 1) << 31));
            return ret;
        }

        public long mod(long a) {
            while (a >= mod) a -= mod;
            while (a < 0) a += mod;
            return a;
        }

        private long[] makePows(long M, int n) {
            long[] ret = new long[n + 1];
            ret[0] = 1;
            for (int i = 1; i <= n; i++) ret[i] = mul(ret[i - 1], M);
            return ret;
        }

        public void add(long x) {
            hs[hp + 1] = mul(hs[hp], M) + x;
            if (hs[hp + 1] >= mod) hs[hp + 1] -= mod;
            hp++;
        }

        public long h(int l, int r) {
            assert l <= r;
            return mod(hs[r] - mul(hs[l], pows[r - l]));
        }
    }

    private static final int mod = 1_000_000_007;

    public boolean[] canMakePalindromeQueries(String s, int[][] queries) {
        int len = s.length();
        int mid = len / 2;
        RollingHash61 left = new RollingHash61(mod, mid), right = new RollingHash61(mod, mid);
        int[][] charMem = new int[len + 1][26];
        for (int i = 0; i < len; ++i) {
            int o = s.charAt(i) - 'a';
            if (i < len / 2) {
                left.add(o);
                right.add(s.charAt(len - i - 1) - 'a');
            }
            for (int j = 0; j < 26; ++j) {
                charMem[i + 1][j] = charMem[i][j];
                if (j == o) {
                    charMem[i + 1][j] += 1;
                }
            }
        }

        boolean[] res = new boolean[queries.length];
        for (int i = 0; i < queries.length; ++i) {
            int a = queries[i][0], b = queries[i][1], c = queries[i][2], d = queries[i][3];
            int mc = len - 1 - d, md = len - 1 - c;

            boolean unMovedEqu;
            if (isColl(a, b, mc, md)) {
                int ml = Math.min(a, mc), mr = Math.max(b, md);
                unMovedEqu = left.h(0, ml) == right.h(0, ml) && left.h(mr + 1, mid) == right.h(mr + 1, mid);
                if (unMovedEqu) {
                    if ((ml == a && mr == b) || (ml == mc && mr == md)) {
                        unMovedEqu = diffNum(charMem, ml, mr, len) == 0;
                    } else {
                        int shared = Math.min(b, md) - Math.max(mc, a) + 1;
                        unMovedEqu = diffNum(charMem, ml, mr, len) == 0 && diffNum(charMem, a, b, len) <= shared;
                        if (unMovedEqu) {
                            if (a < mc) {
                                unMovedEqu = diffNumLarge(charMem, a, b, a, mc - 1, len)
                                        && diffNumLarge(charMem, c, d, b + 1, md, len);
                            } else {
                                unMovedEqu = diffNumLarge(charMem, a, b, md + 1, b, len)
                                        && diffNumLarge(charMem, c, d, mc, a - 1, len);
                            }
                        }
                    }
                }
            } else {
                int[] ml = {Math.min(a, mc), Math.min(b, md)}, mr = {Math.max(a, mc), Math.max(b, md)};
                unMovedEqu = left.h(0, ml[0]) == right.h(0, ml[0]) && left.h(ml[1] + 1 , mr[0]) == right.h(ml[1] + 1 , mr[0])
                        && left.h(mr[1] + 1, mid) == right.h(mr[1] + 1, mid);
                if (unMovedEqu) {
                    unMovedEqu = diffNum(charMem, a, b, len) == 0 && diffNum(charMem, c, d, len) == 0;
                }
            }
            res[i] = unMovedEqu;
        }
        return res;
    }

    private boolean isColl(int a, int b, int c, int d) {
        return !(a > d || b < c);
    }

    private int diffNum(int[][] charMem, int l, int r, int len) {
        int mc = len - 1 - r, md = len - 1 - l;
        int add = 0;
        for (int i = 0; i < 26; ++i) {
            int n1 = charMem[r + 1][i] - charMem[l][i];
            int n2 = charMem[md + 1][i] - charMem[mc][i];
            if (n1 > n2) {
                add += n1 - n2;
            }
        }
        return add;
    }

    private boolean diffNumLarge(int[][] charMem, int l1, int r1, int l2, int r2, int len) {
        int t = len - 1 - r2;
        r2 = len - 1 - l2;
        l2 = t;
        for (int i = 0; i < 26; ++i) {
            int n1 = charMem[r1 + 1][i] - charMem[l1][i];
            int n2 = charMem[r2 + 1][i] - charMem[l2][i];
            if (n1 < n2) {
                return false;
            }
        }
        return true;
    }
}