35. Longest Alternating Binary Substring with Limited Flips

Origin: Longest Alternating Binary Substring with Limited Flips

Given a binary string s and an integer k, find the length of the longest substring that can be made alternating (0101… or 1010…) by flipping at most k bits.

交替二进制串：相邻字符不同，如 0101 或 1010。可以翻转最多 k 个字符使其变成交替串，求最长子串长度。

Example 1

Input: s = "010101", k = 0

Output: 6

Explanation: 已经是交替串，0 次翻转，长度 6。

Example 2

Input: s = "1001101", k = 2

Output: 7

Explanation: 目标交替串 “1010101”，和原串 “1001101” 在索引 2 和 3 不匹配，翻转 2 个字符即可，长度 7。

Input Format

• 第一行：二进制字符串 s
• 第二行：整数 k（最多翻转次数）

Constraints

• 0 <= s.length <= 100000
• s 只包含 ‘0’ 和 ‘1’
• 0 <= k <= s.length

Output Format

返回一个整数：最长可交替子串的长度。

Sample Input 0

1
0

Sample Output 0

1

Sample Input 1

0
0

Sample Output 1

1

---

函数契约

// 输入：s（二进制字符串），k（最多翻转次数）
// 输出：最长可交替子串的长度
// 边界：空字符串 → 0；单字符 → 1；k=0 → 找已有的最长交替子串

边界表

场景	返回什么
空字符串	0
单字符	1
k=0	已有最长交替子串
k >= n	整个串（全部翻转成交替）
正常	翻转 <= k 次能得到的最大长度

Resolution

我的解法（滑动窗口，两种模式各跑一次）

function longestAlternatingSubstring(s: string, k: number): number {
    if (!s.length) return 0
    let maxLength = 0
    for (const start of ['01', '10']) {
        let left = 0, mismatch = 0
        for (let right = 0; right < s.length; right++) {
            if (s[right] !== start[right % 2]) {
                mismatch++
            }
            while (mismatch > k) {
                if (s[left] !== start[left % 2]) {
                    mismatch--
                }
                left++
            }
            maxLength = Math.max(maxLength, right - left + 1)
        }
    }
    return maxLength
}

解题思路

交替串只有两种模式：0101... 和 1010...。对每种模式各跑一次滑动窗口，取最大值。

滑动窗口内维护”不匹配数”：

• right 扩展时，如果 s[right] 不等于目标模式的对应字符，mismatch +1
• mismatch > k 时收缩 left，收缩时如果 left 位置不匹配就 mismatch -1
• 每轮更新最大长度

为什么不固定 left 的模式？ 第一次写的版本用 s[left] 判断模式，但 left 移动后 s[left] 可能变，模式跟着变，而 notGoods 里的索引是按之前的模式算的，导致不一致。固定模式（‘01’ 或 ‘10’）不依赖 left 的值，更稳定。

复杂度

• 时间：O(n)，两次滑动窗口各 O(n)
• 空间：O(1)，只用几个变量

参考来源

• 相关文章：算法解题流程：从读题到提交的七步
• 相关题目：29. Max Unique Substring Length in a Session — 滑动窗口