P3200. 完美走位

解题思路

注意，本题 替换子串得到平衡字符串 以及 最小覆盖子串 几乎完全一致。 重点在于如何将原问题转化为 覆盖子串 的问题。

题目条件

题目有两个重要条件：

1. 完美走位字符串 是指字符串中 A、S、D、W 四种字符出现次数相等的字符串 2. s.length 是 4 的倍数

问题转化

对于长度为 len(s) 的原字符串 s 来说，为了使其转变为一个 完美走位字符串，其中 A、S、D、W 四种字符出现次数应该均为：

原字符串 s 中各个字符出现的次数可以用哈希表 cnt_s = Counter(s) 进行统计。 对于出现次数多于 num = len(s) // 4 的字符 ch，应该修改 cnt_s[ch] - len(s) // 4 个字符为其他出现次数少于 num = len(s) // 4 的字符，才能够使得 s 变为一个 完美走位字符串。

示例说明

以示例四为例，s = "AAAAADDD"，字符 "A" 出现的次数为 5，字符 "D" 应该修改 3，而 num = len(s) // 4 = 2，需要修改 3 个 "A" 和 1 个 "D" 为剩余两种字符，才能使得 s 变为完美走位字符串。 故我们需要找到包含 3 个 "A" 和 1 个 "D" 的 最短子串。

最终结论

因此这个问题就转变为了：找到覆盖 `cnt_s[ch] - len(s) // 4` 个的字符 `ch`（`ch` 满足条件 `cnt_s[ch] > len(s) // 4`）的最短子串。 需要覆盖的子串中所出现的字符以及次数，可以用另一个哈希表 cnt_sub 储存。

那么这个问题就和 最小覆盖子串 完全一致了，直接 滑窗三问三答 解决即可。

上述逻辑整理为代码即：

复杂度分析 设走位记录长度为 n。统计原字符串中各字符出现次数的 cnt_s 需要遍历一次字符串，O(n)；由 cnt_s 导出需要被替换覆盖的字符表 cnt_sub 只涉及至多 4 种字符，O(1)。滑窗阶段，right 从头到尾走一遍，left 只会单调右移、累计移动量不超过 n，每个字符至多进窗一次、出窗一次；每一步的 check 只比较 cnt_sub 中至多 4 个键（字符只有 A、S、D、W 四种），是常数时间。因此滑窗整体为 O(n)，总时间复杂度 O(n)。空间上，cnt_s、cnt_sub、cnt_win 三个哈希表都至多存 4 个键，为 O(1)；算上读入的字符串本身则是 O(n)。题目给出 n 上限为 10^5，线性做法轻松通过。