LeetCode 双周赛 112
T1. 判断通过操作能否让字符串相等 I（Easy）
- 标签：模拟
T2. 判断通过操作能否让字符串相等 II（Medium）
- 标签：模拟、计数、排序
T3. 几乎唯一子数组的最大和（Medium）
- 标签：滑动窗口、计数
T4. 统计一个字符串的 k 子序列美丽值最大的数目（Hard）
- 标签：枚举、贪心、排序、乘法原理、组合数
T1. 判断通过操作能否让字符串相等 I（Easy）
https://leetcode.cn/problems/check-if-strings-can-be-made-equal-with-operations-i/
题解（模拟）
因为只能交换距离偶数倍的位置，因此相当于比较两个字符串相同奇偶性下标上的元素是否相等。
- 写法 1：基于散列表
class Solution {
fun canBeEqual(s1: String, s2: String): Boolean {
return setOf(s1[0], s1[2]) == setOf(s2[0], s2[2]) && setOf(s1[1], s1[3]) == setOf(s2[1], s2[3])
}
}
- 写法 2：基于字符串
class Solution:
def checkStrings(self, s1: str, s2: str) -> bool:
return sorted(s1[0::2]) == sorted(s2[0::2]) and sorted(s1[1::2]) == sorted(s2[1::2])
复杂度分析：
- 时间复杂度：
- 空间复杂度：
T2. 判断通过操作能否让字符串相等 II（Medium）
https://leetcode.cn/problems/check-if-strings-can-be-made-equal-with-operations-ii/
题解（模拟）
同上，分别统计奇偶下标上的元素个数是否相等。
写法 1：基于计数；
class Solution {
fun checkStrings(s1: String, s2: String): Boolean {
val U = 26
val cnts = Array(2) { IntArray(U) }
for ((i, e) in s1.withIndex()) {
cnts[i % 2][e - 'a']++
}
for ((i, e) in s2.withIndex()) {
cnts[i % 2][e - 'a']--
}
return cnts[0].all {it == 0} && cnts[1].all {it == 0}
}
}
复杂度分析：
- 时间复杂度：
线性遍历时间与计数时间；
- 空间复杂度：
计数数组空间。
写法 2：基于字符串：
class Solution:
def checkStrings(self, s: str, t: str) -> bool:
return all(sorted(s[p::2]) == sorted(t[p::2]) for p in range(2))
复杂度分析：
- 时间复杂度：
排序时间；
- 空间复杂度：
构造字符串空间。
T3. 几乎唯一子数组的最大和（Medium）
https://leetcode.cn/problems/maximum-sum-of-almost-unique-subarray/
题解（滑动窗口 + 计数）
滑动窗口模板题，维护窗口中不同元素的种类数和总和：
class Solution {
fun maxSum(nums: List<Int>, m: Int, k: Int): Long {
var cnts = HashMap<Int, Int>()
var type = 0
var sum = 0L
var ret = 0L
for (j in nums.indices) {
// 滑入
cnts[nums[j]] = cnts.getOrDefault(nums[j], 0) + 1
if (1 == cnts[nums[j]]!!) type++
sum += nums[j]
// 滑出
if (j >= k) {
val i = j - k
cnts[nums[i]] = cnts[nums[i]]!! - 1
if (0 == cnts[nums[i]]) type --
sum -= nums[i]
}
// 记录
if (j >= k - 1 && type >= m) {
ret = max(ret, sum)
}
}
return ret
}
}
复杂度分析：
- 时间复杂度：
- 空间复杂度：
T4. 统计一个字符串的 k 子序列美丽值最大的数目（Hard）
https://leetcode.cn/problems/count-k-subsequences-of-a-string-with-maximum-beauty/
问题分析
-
问题目标： 求所有长为
的子序列中美丽值是最大值的子序列数目；
-
问题要件： 先计算长为
- 关键信息 1： 子序列要选择不重复的字母；
- 关键信息 2： 同一个字符在原字符串中的不同位置可以构造不同子序列；
-
核心变量：
是 字符
的出现次数，美丽值是子序列中字符的
-
边界情况： 既然子序列要选择不重复的字母，那么存在边界情况，当
。
题解一（暴力枚举 + 乘法原理）
最简单的做法，我们可以枚举所有可能的 子序列，并记录出现最大美丽值的方案数，怎么实现呢？
- 方法 1 - 考虑到子序列需要保留原字符串的顺序，直接的想法是枚举字符串中的每个下标
选和不选，但是时间复杂度是
显然不成立；
- 方法 2 - 事实上我们不需要从原字符串的角度枚举，而是可以从字符集的角度枚举，那样时间复杂度就可以用乘法原理来优化。比如说
a的出现次数是，而
b的出现次数是，那么所有
a与b可以构造的子序列方案数就是2 * 3 = 6。
那么，方法会不会超时呢，我们来简单分析下：
由于字符集的大小 最多只有
个，那么子序列的方案数最多有
个，而由于
大于
的方案是不存在的，因此合法的方案数最多只有
约等于
。只要我们保证求解每个子问题的时间复杂度是
的话是可以通过的。
枚举实现：
class Solution {
fun countKSubsequencesWithMaxBeauty(s: String, k: Int): Int {
val MOD = 1000000007
// 计数
val cnts = HashMap<Char, Int>()
for (e in s) {
cnts[e] = cnts.getOrDefault(e, 0) + 1
}
val m = cnts.size
if (m < k) return 0 // 特判
// 枚举子序列
val keys = cnts.toList()
var maxCount = 0L
var maxF = 0
// 回溯
fun count(index: Int, size: Int, curF: Int, curCount: Long) {
// 终止条件
if (size == k) {
if (curF > maxF) {
maxF = curF
maxCount = curCount // 更新最大美丽值方案数
} else if (curF == maxF) {
maxCount = (maxCount + curCount) % MOD // 增加方案数
}
return
}
if (size + m - index < k) return // 剪枝（长度不够）
for (i in index until m) {
val (c, cnt) = keys[i]
count(i + 1, size + 1, curF + cnt, curCount * cnt % MOD /* 乘法原理 */)
}
}
count(0, 0, 0, 1)
return maxCount.toInt()
}
}
复杂度分析：
- 时间复杂度：
其中
为字符种类 ；
- 空间复杂度：
散列表空间与递归栈空间。
题解二（排序 + 贪心 + 乘法原理）
考虑 的边界情况：
显然需要选择 值最大的
个字母，如果存在
个字母的
等于最大值，那么存在
种方案。这说明我们没必要枚举所有字母的子序列： 由于子序列中的字符是不重复的，因此
子序列必然要选择
值最大的
个字母，我们可以将字母按照
倒序排序，优先取
更大的字母。
具体实现上：
我们将字母按照 分桶排序，如果桶内字母数量
小于等于
，那么桶内元素都需要选择，否则还要计算桶内元素选择
个的方案数：
- 选择桶内所有元素，方案数为
- 选择桶内部分元素，方案数为
其中涉及到幂运算，本质是倍增思想：
// 快速幂 x^n
private fun powM(a: Int, b: Int, mod: Int) : Long {
var x = a.toLong()
var n = b.toLong()
var ret = 1L
while (n > 0L) {
if (n % 2 == 1L) ret = ret * x % mod
x = x * x % mod
n /= 2
}
return ret
}
其中涉及到 组合数：
- 计算式：
// 组合数计算公式 O(k)
private fun comb(n: Int, k: Int, mod: Int) : Int {
var ret = 1L
for (i in 1 .. k) {
ret = ret * (n - i + 1) / i % mod
}
return ret.toInt()
}
- 递推式（杨辉三角）：
// 递归 O(n^2)
private fun comb(n: Int, k: Int, mod: Int) : Int {
if (n == k) {
return 1
} else if (k == 1) {
return n
} else {
return (comb(n - 1, k - 1, mod) + comb(n - 1, k, mod)) % mod
}
}
// 迭代 O(n^2)
private fun comb(n: Int, k: Int, mod: Int) : Int {
val c = Array(n + 1) { IntArray(n + 1) }
for (i in 1 .. n) {
c[i][0] = 1
c[i][i] = 1
for (j in 1 until i) {
c[i][j] = (c[i-1][j] + c[i-1][j-1]) % mod
}
}
return c[n][k]
}
- 卢卡斯定理： 当问题规模很大，且模不太大时使用 Lucas 定理。
// 组合数计算公式
private fun comb(n: Long, k: Long, mod: Int) : Int {
var n = n
var ret = 1L
for (i in 1 .. k) {
ret = ret * n-- / i % mod
}
return ret.toInt()
}
// 卢卡斯定理
fun Lucas(n: Long, k: Long, mod: Int) : Long {
if (k == 0L) return 1L;
return (comb(n % mod, k % mod, mod) * Lucas(n / mod, k / mod, mod)) % mod;
}
完整代码：
class Solution {
fun countKSubsequencesWithMaxBeauty(s: String, k: Int): Int {
val MOD = 1000000007
// 计数
val cnts = HashMap<Char, Int>()
var maxCnt = 0
for (e in s) {
cnts[e] = cnts.getOrDefault(e, 0) + 1
maxCnt = max(maxCnt, cnts[e]!!)
}
val m = cnts.size
if (m < k) return 0 // 特判
// 有序集合
val map = TreeMap<Int, Int>() { c1, c2 ->
c2 - c1
}
// 二次频率
for ((_, c) in cnts) {
map[c] = map.getOrDefault(c, 0) + 1
}
val cntCnts = map.toList()
// println(cntCnts.joinToString())
// 构造方案
var ret = 1L
var leftK = k
for ((cnt, K) in cntCnts) {
if (K > leftK) {
ret = ret * powM(cnt, leftK, MOD) * comb(K, leftK, MOD) % MOD
} else {
ret = ret * powM(cnt, K, MOD) % MOD
}
leftK -= K
if (leftK <= 0) break
}
return ret.toInt()
}
// 组合数计算公式 C_n^k
private fun comb(n: Int, k: Int, mod: Int) : Int {
if (n == k) {
return 1
} else if (k == 1) {
return n
} else {
return (comb(n - 1, k - 1, mod) + comb(n - 1, k, mod)) % mod
}
}
// 快速幂 x^n
private fun powM(x_: Int, n_: Int, mod: Int) : Long {
var x = x_.toLong()
var n = n_.toLong()
var ret = 1L
while (n > 0L) {
if (n % 2 == 1L) ret = ret * x % mod
x = x * x % mod
n /= 2
}
return ret
}
}
Python 中组合数和幂运算可以很方便地使用库函数：
class Solution:
def countKSubsequencesWithMaxBeauty(self, s: str, k: int) -> int:
MOD = 10 ** 9 + 7
ans = 1
cnt = Counter(Counter(s).values())
for c, num in sorted(cnt.items(), reverse=True): # 二次计数
if num >= k:
return ans * pow(c, k, MOD) * comb(num, k) % MOD
ans *= pow(c, num, MOD)
k -= num
return 0
复杂度分析：
- 时间复杂度：
主要时间在枚举字符串的环节；
- 空间复杂度：
推荐阅读
LeetCode 上分之旅系列往期回顾：
