2025-07-10：字符相同的最短子字符串Ⅰ。用go语言，给定一个长度为 n 的二进制字符串 s 和一个允许执行的最大操作次数

2025-07-10：字符相同的最短子字符串Ⅰ。用go语言，给定一个长度为 n 的二进制字符串 s 和一个允许执行的最大操作次数 numOps。

每次操作可以选择字符串中的任意一个位置 i（0 ≤ i < n），将 s[i] 的字符从 '0' 翻转为 '1'，或者从 '1' 翻转为 '0'。

目标是在进行最多 numOps 次这样的翻转操作后，使得字符串中最长的连续相同字符子串的长度尽可能小。

请返回经过这些操作之后，能够达到的最小的最长连续相同字符子串长度。

1 <= n == s.length <= 1000。

s 仅由 '0' 和 '1' 组成。

0 <= numOps <= n。

输入: s = "000001", numOps = 1。

输出: 2。

解释:

将 s[2] 改为 '1'，s 变为 "001001"。最长的所有字符相同的子串为 s[0..1] 和 s[3..4]。

题目来自力扣3398。

解决思路

1. 1. 初始检查：
   • • 首先计算将字符串转换为全 '0' 或全 '1' 所需的最小操作次数。如果 numOps 足够大（即可以完全统一字符串），则直接返回 1（因为所有字符相同，最长连续子串长度为 1）。
   • • 具体来说：
     • • 统计字符串中与索引奇偶性不匹配的字符数量 cnt（即 (s[i] - '0') ^ (i % 2) 的和）。cnt 表示将字符串转换为交替 '0' 和 '1' 的最小操作次数。
     • • 如果 min(cnt, n - cnt) <= numOps，则可以完全统一或交替，返回 1。
2. 2. 处理无法完全统一或交替的情况：
   • • 如果不能通过操作使字符串完全统一或交替，则需要找到一种翻转策略，使得最长的连续相同字符的子串尽可能短。
   • • 统计原始字符串中连续相同字符的子串的长度分布。例如，"000001" 可以分解为 "00000"（长度为 5）和 "1"（长度为 1）。
   • • 使用一个数组 h，其中 h[k] 存储所有长度为 k 的连续相同字符的子串的信息（包括原始长度和分段数）。
3. 3. 贪心策略：
   • • 每次操作优先拆分最长的连续子串。具体来说：
     • • 找到当前最长的连续子串长度 i。
     • • 取出一个长度为 i 的子串，将其拆分为 seg + 1 段（seg 初始为 1），这样每段的长度最多为 ceil(i / (seg + 1))。
     • • 将拆分后的信息重新存入 h。
     • • 重复此过程直到用完所有操作或无法进一步拆分。
4. 4. 结果确定：
   • • 操作完成后，当前最长的连续子串的长度即为答案。

具体步骤

1. 1. 初始检查：
   • • 对于 s = "000001"，n = 6。
   • • 计算 cnt：
     • • s[0] = '0'，0 ^ 0 = 0。
     • • s[1] = '0'，0 ^ 1 = 1。
     • • s[2] = '0'，0 ^ 0 = 0。
     • • s[3] = '0'，0 ^ 1 = 1。
     • • s[4] = '0'，0 ^ 0 = 0。
     • • s[5] = '1'，1 ^ 1 = 0。
     • • cnt = 0 + 1 + 0 + 1 + 0 + 0 = 2。
   • • min(2, 6 - 2) = 2，numOps = 1，2 > 1，无法完全统一或交替。
2. 2. 统计连续子串长度：
   • • "000001" 分解为 "00000"（'0'，长度 5）和 "1"（'1'，长度 1）。
   • • h[5] = [{5, 1}]，h[1] = [{1, 1}]。
3. 3. 操作过程：
   • • 初始最长子串长度 i = 5。
   • • 第一次操作：
     • • 取出 h[5] 的 {5, 1}，seg = 1。
     • • 拆分为 seg + 1 = 2 段，每段长度 max(5 / 2) = 3。
     • • 更新 h[3] = [{5, 2}]。
   • • 操作后 h：
     • • h[3] = [{5, 2}]（表示有 2 段，每段最多 3）。
     • • h[1] = [{1, 1}]。
   • • 最长子串长度现在是 3，但 numOps 已用完。
4. 4. 结果：
   • • 最长子串长度为 3，但实际拆分后的字符串是 "000" 和 "00"（因为 5 拆分为 3 和 2），所以最长是 3。
   • • 但根据示例，实际翻转 s[2] 得到 "001001"，最长是 2。这里可能与代码逻辑不完全一致。

代码逻辑修正

• • 代码中 h 的设计可能更复杂，实际拆分可能是将 5 拆分为 2 和 3（ceil(5 / 2) 和 floor(5 / 2)），因此 h[3] 和 h[2] 会被更新。
• • 在 i = 2 时直接返回 2，可能是提前终止的条件。

时间复杂度和空间复杂度

• • 时间复杂度：
  • • 初始检查：遍历字符串一次，O(n)。
  • • 统计连续子串长度：遍历字符串一次，O(n)。
  • • 操作过程：每次操作需要 O(n) 时间（因为可能需要遍历 h 数组），最多 numOps 次操作，O(n * numOps)。
  • • 总体：O(n * numOps)。
• • 空间复杂度：
  • • h 数组大小为 O(n)，存储的子串信息最多 O(n)。
  • • 总体：O(n)。

总结

• • 算法通过贪心策略优先拆分最长的连续子串，确保操作后最长子串尽可能短。
• • 时间复杂度和空间复杂度均与输入规模线性相关，效率较高。

Go完整代码如下：

.

package main

import (
    "fmt"
)

func minLength(s string, numOps int)int {
    n := len(s)
    cnt := 0
    for i, b := range s {
        cnt += (int(b) ^ i) & 1
    }
    if min(cnt, n-cnt) <= numOps {
        return1
    }

    type pair struct{ k, seg int }
    h := make([][]pair, n+1)
    k := 0
    for i := 0; i < n; i++ {
        k++
        // 到达连续相同子串的末尾
        if i == n-1 || s[i] != s[i+1] {
            h[k] = append(h[k], pair{k, 1}) // 原始子串长度，段数
            k = 0
        }
    }

    i := n
    forrange numOps {
        forlen(h[i]) == 0 {
            i--
        }
        if i == 2 {
            return2
        }
        p := h[i][len(h[i])-1]
        h[i] = h[i][:len(h[i])-1]
        p.seg++
        maxSeg := p.k / p.seg
        h[maxSeg] = append(h[maxSeg], p)
    }

    forlen(h[i]) == 0 {
        i--
    }
    return i
}

func main() {
    s := "000001"
    numOps := 1
    result := minLength(s, numOps)
    fmt.Println(result)
}

Python完整代码如下：

.

# -*-coding:utf-8-*-

def minLength(s: str, numOps: int) -> int:
    n = len(s)
    cnt = 0
    # 统计 s 中奇偶位置与字符的 XOR 个数，用于判断是否能通过翻转变成交替串
    for i, ch in enumerate(s):
        cnt += (ord(ch) ^ i) & 1
    if min(cnt, n - cnt) <= numOps:
        return1

    # 构造连续相同子串长度数组
    h = [[] for _ in range(n+1)]
    k = 0
    for i in range(n):
        k += 1
        # 到达连续子串结尾
        if i == n-1 or s[i] != s[i+1]:
            # pair: (原始子串长度k, 段数1)
            h[k].append([k, 1])
            k = 0

    i = n
    while numOps > 0:
        while i > 0 and len(h[i]) == 0:
            i -= 1
        if i == 2:
            return2

        p = h[i].pop()
        # p段数增加1，即将长段拆成更多段，从而缩短最长连续串
        p[1] += 1
        maxSeg = p[0] // p[1]
        h[maxSeg].append(p)
        numOps -= 1

    while i > 0 and len(h[i]) == 0:
        i -= 1
    return i

if __name__ == "__main__":
    s = "000001"
    numOps = 1
    result = minLength(s, numOps)
    print(result)