P3204. 求满足条件的最长子串的长度

解题思路

本题属于典型的不定滑窗问题。我们可以维护两个计数变量 alpha_num 和 digit_num，用来分别表示窗口中的字母个数和数字个数。滑窗三问三答将围绕这两个变量来进行。

滑窗三问

Q1：对于每一个右指针 right 所指的元素 ch，做什么操作？

Q2：什么时候要令左指针 left 右移？left 对应的元素做什么操作？while 中的循环不变量是什么？

Q3：什么时候进行 ans 的更新？

滑窗三答

A1：根据 ch 的类型（数字/字母），修改对应的计数变量（alpha_num / digit_num）。

A2：窗口中字母的个数等于 2，即 alpha_num = 2，left 指针右移，同时根据右移时经过的元素类型修改计数变量，直到 alpha_num = 1。

A3：alpha_num = 1 且 digit_num > 0，说明窗口中仅存在一个字母和若干数字，此时可以更新答案 ans。

思路展开 代码用两个计数变量刻画窗口状态：alpha_num 记录窗口内字母的个数，digit_num 记录窗口内数字的个数，left 是窗口左边界。right 逐个吞入字符 ch：是数字就 digit_num 加一，是字母就 alpha_num 加一。窗口内允许的字母数至多为 1，所以一旦 alpha_num 变成 2（新进来的字母是第二个字母），就进入收缩：left 不断右移，同时按被移出字符的类型回退相应计数，直到 alpha_num 重新降为 1，此时窗口里保留的是靠右的那个字母以及它周围的数字。每一步处理完后检查：若 alpha_num 恰为 1 且 digit_num 大于 0，说明窗口正好是一个字母加若干数字的合法子串，用 digit_num + 1（即窗口长度，与 right - left + 1 等价）更新答案。这样每个右端点都对应了以它结尾的最长合法窗口，全程取最大即为答案。

复杂度分析 设字符串长度为 n。right 从头到尾遍历一次，left 只会单调右移、累计移动量不超过 n，每个字符至多进窗一次、出窗一次，判断字符类型和更新计数都是常数操作，因此时间复杂度为 O(n)。除输入字符串外只用了 alpha_num、digit_num、left、ans 四个变量，额外空间复杂度 O(1)。

边界与注意事项

• 字符串全是数字：alpha_num 永远为 0，更新条件 alpha_num == 1 永远不成立，ans 保持初始值 -1 输出，符合题面中不存在满足要求的子串时返回 -1 的约定。
• 字符串全是字母：digit_num 收缩后为 0，digit_num > 0 不成立，同样输出 -1。
• 合法子串要求恰好 1 个字母，且字母可以在窗口任意位置（开头、中间、结尾都行），代码只控制字母个数、不限制其位置，与题意一致。
• 答案更新用 digit_num + 1 而非只数数字个数，别忘了把那 1 个字母也算进长度里。