7021. Check if Strings Can be Made Equal With Operations I
给你两个字符串 s1 和 s2 ，两个字符串的长度都为 4 ，且只包含 小写 英文字母。
你可以对两个字符串中的 任意一个 执行以下操作 任意 次：
- 选择两个下标 i 和 j 且满足 j - i = 2 ，然后 交换 这个字符串中两个下标对应的字符。
如果你可以让字符串 s1 和 s2 相等，那么返回 true ，否则返回 false 。
测试样例
输入：s1 = "abcd", s2 = "dacb"
输出：false
解释：无法让两个字符串相等。
解答：枚举一下交换情况，判断是否相等。
class Solution {
public boolean canBeEqual(String s1, String s2) {
return helper(s1.charAt(0), s1.charAt(2), s2.charAt(0), s2.charAt(2))
&& helper(s1.charAt(1), s1.charAt(3), s2.charAt(1), s2.charAt(3));
}
private boolean helper(char c1, char c2, char c3, char c4) {
if (c1 == c3 && c2 == c4) {
return true;
} else if (c1 == c4 && c2 == c3) {
return true;
}
return false;
}
}7005. Check if Strings Can be Made Equal With Operations II
给你两个字符串 s1 和 s2 ，两个字符串长度都为 n ，且只包含 小写 英文字母。
你可以对两个字符串中的 任意一个 执行以下操作 任意 次：
- 选择两个下标 i 和 j ，满足 i < j 且 j - i 是 偶数，然后 交换 这个字符串中两个下标对应的字符。
如果你可以让字符串 s1 和 s2 相等，那么返回 true ，否则返回 false 。
测试样例：
输入：s1 = "abe", s2 = "bea"
输出：false
解释：
无法让两个字符串相等。
解答: 奇偶位统计即可。
class Solution {
public boolean checkStrings(String s1, String s2) {
return helper(s1, s2, 0) && helper(s1, s2, 1);
}
private boolean helper(String s1, String s2, int st) {
int[] count = new int[26];
for (int i = st; i < s1.length(); i += 2) {
count[s1.charAt(i) - 'a'] += 1;
}
for (int i = st; i < s2.length(); i += 2) {
count[s2.charAt(i) - 'a'] -= 1;
}
for (int i = 0; i < count.length; ++i) {
if (count[i] != 0) {
return false;
}
}
return true;
}
}6989. Maximum Sum of Almost Unique Subarray
给你一个整数数组 nums 和两个正整数 m 和 k 。
请你返回 nums 中长度为 k 的 几乎唯一 子数组的 最大和 ，如果不存在几乎唯一子数组，请你返回 0 。
如果 nums 的一个子数组有至少 m 个互不相同的元素，我们称它是 几乎唯一 子数组。
子数组指的是一个数组中一段连续 非空 的元素序列。
测试样例：
输入：nums = [2,6,7,3,1,7], m = 3, k = 4
输出：18
解释：
总共有 3 个长度为 k = 4 的几乎唯一子数组。分别为 [2, 6, 7, 3] ，[6, 7, 3, 1] 和 [7, 3, 1, 7] 。这些子数组中，和最大的是 [2, 6, 7, 3] ，和为 18 。
解答: 双指针配合HashMap统计当前数组的distinct num数，满足要求就记录一下最大值。
class Solution {
public long maxSum(List<Integer> nums, int m, int k) {
int pos = 0;
Iterator<Integer> left = nums.iterator(), right = nums.iterator();
long best = 0, cur = 0;
HashMap<Integer, Integer> map = new HashMap<>();
while (right.hasNext()) {
int num = right.next();
++pos;
cur += num;
map.put(num, map.getOrDefault(num, 0) + 1);
if (pos >= k) {
if (map.size() >= m) {
best = Math.max(best, cur);
}
int remove = left.next();
int count = map.get(remove);
cur -= remove;
if (count == 1) {
map.remove(remove);
} else {
map.put(remove, count - 1);
}
}
}
return best;
}
}8013. Number of Beautiful Integers in the Range
给你一个字符串 s 和一个整数 k 。
k 子序列指的是 s 的一个长度为 k 的 子序列 ，且所有字符都是 唯一 的，也就是说每个字符在子序列里只出现过一次。
定义 f(c) 为字符 c 在 s 中出现的次数。
k 子序列的 美丽值 定义为这个子序列中每一个字符 c 的 f(c) 之 和 。
比方说，s = "abbbdd" 和 k = 2 ，我们有：
- f('a') = 1, f('b') = 3, f('d') = 2
- s 的部分 k 子序列为：
- "abbbdd" -> "ab" ，美丽值为 f('a') + f('b') = 4
- "abbbdd" -> "ad" ，美丽值为 f('a') + f('d') = 3
- "abbbdd" -> "bd" ，美丽值为 f('b') + f('d') = 5
请你返回一个整数，表示所有 k 子序列 里面 美丽值 是 最大值 的子序列数目。由于答案可能很大，将结果对 109 + 7 取余后返回。
一个字符串的子序列指的是从原字符串里面删除一些字符（也可能一个字符也不删除），不改变剩下字符顺序连接得到的新字符串。
注意：
- f(c) 指的是字符 c 在字符串 s 的出现次数，不是在 k 子序列里的出现次数。
- 两个 k 子序列如果有任何一个字符在原字符串中的下标不同，则它们是两个不同的子序列。所以两个不同的 k 子序列可能产生相同的字符串。
测试样例：
输入：s = "bcca", k = 2
输出：4
解释：
s 中我们有 f('a') = 1 ，f('b') = 1 和 f('c') = 2 。
s 的 k 子序列为：
bcca ，美丽值为 f('b') + f('c') = 3
bcca ，美丽值为 f('b') + f('c') = 3
bcca ，美丽值为 f('b') + f('a') = 2
bcca ，美丽值为 f('c') + f('a') = 3
bcca ，美丽值为 f('c') + f('a') = 3
总共有 4 个 k 子序列美丽值为最大值 3 。
所以答案为 4 。
解答: 这道题目其实很简单。先统计一下每个字符出现的次数，然后寻找最大的K的次数（如果无法寻找到K个，就返回0）。注意的是，最小的一个次数，可能会有多种可能。这时候还需要利用组合，先从中寻出n个。
class Solution {
private static final int mod = 1_000_000_007;
public int countKSubsequencesWithMaxBeauty(String s, int k) {
int[] freq = new int[26];
for (int i = 0; i < s.length(); ++i) {
freq[s.charAt(i) - 'a'] += 1;
}
Arrays.sort(freq);
int count = 0;
for (int i = 25; i >= 0; --i) {
if (freq[i] > 0) {
++count;
}
}
if (count < k) {
return 0;
}
long res = 1;
for (int i = 0; i < k; ++i) {
res = (res * freq[25 - i]) % mod;
}
count = 0;
int bigger = 0;
for (int i = 0; i < 26; ++i) {
if (freq[i] == freq[26 - k]) {
count += 1;
} else if (freq[i] > freq[26 - k]) {
++bigger;
}
}
res = (res * C(k - bigger, count)) % mod;
return (int) res;
}
private int C(int n, int m) {
if (n == m) {
return 1;
} else if (n == 1) {
return m;
} else {
return (C(n - 1, m - 1) + C(n, m - 1)) % mod;
}
}
}