---

1573. 分割字符串的方案数

• 标签：数学、字符串
• 难度：中等

题目链接

• 1573. 分割字符串的方案数 - 力扣

题目大意

描述：给定一个二进制字符串 $s$（只包含 $0$ 和 $1$）。可以将字符串分割成三个非空子字符串。

要求：返回分割方式的数目，使得三个子字符串中 $1$ 的个数相同。结果对 $10^9 + 7$ 取模。

说明：

• $1 \le s.length \le 3 \times 10^4$。

示例：

• 示例 1：

输入：s = "10101"
输出：4
解释：总共有 4 种方法将 s 分割成含有 '1' 数目相同的三个子字符串。
"1|010|1"
"1|01|01"
"10|10|1"
"10|1|01"

• 示例 2：

输入：s = "1001"
输出：0

解题思路

思路 1：组合数学

1. 核心思想

设 $total$ 为字符串中 $1$ 的总数。

• 如果 $total \% 3 \neq 0$，不可能均分，返回 $0$。
• 如果 $total == 0$，在 $n-1$ 个空隙中选择两个位置分割，方案数为 $C(n-1, 2)$。

否则，每段应有 $target = total / 3$ 个 $1$。

找到以下位置：

• 第一个 $1$ 的累计数达到 $target$ 的位置 $i$（$\le$第一个分割点的可行范围）
• 累计数达到 $target+1$ 的位置 $i$
• 累计数达到 $2 \times target$ 的位置 $j$
• 累计数达到 $2 \times target + 1$ 的位置 $j$

第一个分割点的可行位置数 = $pos\_first\_end - pos\_first\_start$。
第二个分割点的可行位置数 = $pos\_second\_end - pos\_second\_start$。

方案数 = 两者相乘。

2. 具体步骤

第 1 步：统计 $1$ 的总数 $total$。如果 $total \% 3 \neq 0$，返回 $0$。
如果 $total == 0$，返回 $(n-1) \times (n-2) / 2 \% MOD$。

第 2 步：$target = total / 3$。

第 3 步：遍历整个字符串，记录每个 $1$ 的位置索引 $pos$ 数组。

第 4 步：

• 第一个分割点可以在 $pos[target-1]$ 到 $pos[target]-1$ 之间（即第 $target$ 个 $1$ 和第 $target+1$ 个 $1$ 之间）。
• 第二个分割点可以在 $pos[2target-1]$ 到 $pos[2target]-1$ 之间。

方案数 = $(pos[target] - pos[target-1]) \times (pos[2target] - pos[2target-1]) \% MOD$。

3. 举例说明

以 $s = "10101"$ 为例：

$1$ 的个数 $total=3$，$target=1$。

$1$ 的位置：$[0, 2, 4]$。

• 第一个分割点位置范围：$(pos[0]=0, pos[1]=2)$ → 可以是位置 $1$（只在 $0$ 和 $2$ 之间，即下标 $1$ 到 $1$）。
  实际上，第一个分割将 $[0, 1]$ 个给第一部分，第一部分需要有 $1$ 个 $1$。$1$ 的位置是 $0$，所以第一部分的结束位置 $\ge 0$ 且 $<$ 下一个 $1$ 的位置 $2$。
  所以第一个分割点 $\in [1, 1]$（在第一个 $1$ 后面、第二个 $1$ 前面）。
• 第二个分割点位置范围：$(pos[1]=2, pos[2]=4)$ → 可以是位置 $3$。

方案数 = $(2-0) \times (4-2) = 4$。

但实际上 $s="10101"$ 长度 $5$，可能的三个非空子串的分割方式：

分割点位置 $[i, j]$（$1 \le i < j \le 4$）：

• $[1,2]$：$"1"$, $"0"$, $"101"$ → 1 的个数 $1, 0, 2$。$\times$

  • 不对，第一部分从 $0$ 到 $i-1=0$，即 $"1"$。第二部分从 $i$ 到 $j-1=1$，即 $"0"$。第三部分从 $j$ 到 $4$，即 $"101"$。1 的个数：$1,0,2$，不等。

• $[1,3]$：$"1"$, $"01"$, $"01"$ → $1,1,1$。✓

• $[2,3]$：$"10"$, $"1"$, $"01"$ → $1,1,1$。✓

• $[2,4]$：$"10"$, $"10"$, $"1"$ → $1,1,1$。✓

• $[1,4]$：$"1"$, $"010"$, $"1"$ → $1,1,1$。✓

实际上有 $4$ 种。

$pos[target] - pos[target-1] = pos[1] - pos[0] = 2 - 0 = 2$
$pos[2target] - pos[2target-1] = pos[2] - pos[1] = 4 - 2 = 2$
方案数 $= 2 \times 2 = 4$。✓

思路 1：代码

class Solution:
    def numWays(self, s: str) -> int:
        MOD = 10 ** 9 + 7
        n = len(s)
        ones = [i for i, ch in enumerate(s) if ch == '1']
        total = len(ones)

        if total % 3 != 0:
            return 0
        if total == 0:
            return (n - 1) * (n - 2) // 2 % MOD

        target = total // 3
        # 第一个分割点的可选项数
        left_gap = ones[target] - ones[target - 1]
        # 第二个分割点的可选项数
        right_gap = ones[2 * target] - ones[2 * target - 1]

        return left_gap * right_gap % MOD

思路 1：复杂度分析

• 时间复杂度：$O(n)$。
• 空间复杂度：$O(n)$，存储 $1$ 的位置。