How do I approach the problem of splitting a binary string into three parts?

Start by checking if the total number of '1's in the string is divisible by 3. Then, calculate the positions of '1's and figure out how to split them into three parts with equal '1's.

What should I do if the sum of '1's is not divisible by 3?

If the total number of '1's is not divisible by 3, immediately return 0 because a valid split is not possible.

Why do I need to store the positions of '1's?

Storing the positions of '1's allows you to efficiently find where to split the string into three parts with equal numbers of '1's.

What is the time complexity of the solution?

The time complexity is O(n), where n is the length of the string. This is due to the need to check the positions of all '1's and calculate possible splits.

Can this problem be solved with dynamic programming?

Dynamic programming is not necessary for this problem as it can be solved efficiently with a linear scan of the string and careful counting of valid splits.

#1573

Medium

auto_awesome数学·string

LeetCode 题解工作台

分割字符串的方案数

给你一个二进制串 s （一个只包含 0 和 1 的字符串），我们可以将 s 分割成 3 个非空字符串 s1, s2, s3 （s1 + s2 + s3 = s）。请你返回分割 s 的方案数，满足 s1，s2 和 s3 中字符 '1' 的数目相同。由于答案可能很大，请将它对 10^9 + 7 …

数学字符串

题目描述

给你一个二进制串 s （一个只包含 0 和 1 的字符串），我们可以将 s 分割成 3 个非空字符串 s1, s2, s3 （s1 + s2 + s3 = s）。

请你返回分割 s 的方案数，满足 s1，s2 和 s3 中字符 '1' 的数目相同。

由于答案可能很大，请将它对 10^9 + 7 取余后返回。

示例 1：

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

示例 2：

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

示例 3：

输入：s = "0000"
输出：3
解释：总共有 3 种分割 s 的方法。
"0|0|00"
"0|00|0"
"00|0|0"

示例 4：

输入：s = "100100010100110"
输出：12

提示：

s[i] == '0' 或者 s[i] == '1'
3 <= s.length <= 10^5

lightbulb

解题思路

方法一：计数

我们先遍历字符串 $s$ ，统计其中字符 $1$ 的个数 $cnt$ ，如果 $cnt$ 不能被 $3$ 整除，那么无法分割，直接返回 $0$ 。如果 $cnt$ 为 $0$ ，说明字符串中没有字符 $1$ ，我们可以在 $n-1$ 个位置中任意选择两个位置，将字符串分割成三个子串，那么方案数就是 $C_{n-1}^2$ 。

如果 $cnt \gt 0$ ，我们将 $cnt$ 更新为 $\frac{cnt}{3}$ ，即每个子串中字符 $1$ 的个数。

接下来我们找到第一个子字符串的右边界的最小下标，记为 $i_1$ ，第一个子字符串的右边界的最大下标（不包含），记为 $i_2$ ；第二个子字符串的右边界的最小下标，记为 $j_1$ ，第二个子字符串的右边界的最大下标（不包含），记为 $j_2$ 。那么方案数就是 $(i_2-i_1) \times (j_2-j_1)$ 。

注意答案可能很大，需要对 $10^9+7$ 取模。

时间复杂度 $O(n)$ ，空间复杂度 $O(1)$ 。其中 $n$ 为字符串 $s$ 的长度。

相似题目：

927. 三等分

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

class Solution:
    def numWays(self, s: str) -> int:
        def find(x):
            t = 0
            for i, c in enumerate(s):
                t += int(c == '1')
                if t == x:
                    return i

        cnt, m = divmod(sum(c == '1' for c in s), 3)
        if m:
            return 0
        n = len(s)
        mod = 10**9 + 7
        if cnt == 0:
            return ((n - 1) * (n - 2) // 2) % mod
        i1, i2 = find(cnt), find(cnt + 1)
        j1, j2 = find(cnt * 2), find(cnt * 2 + 1)
        return (i2 - i1) * (j2 - j1) % (10**9 + 7)

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate shows an understanding of the need to first check divisibility by 3.
question_mark
Candidate knows how to identify the positions of '1's efficiently.
question_mark
Candidate considers how to count valid splits based on the positions of '1's.

warning

常见陷阱

外企场景

error
Ignoring the requirement that the total number of '1's must be divisible by 3.
error
Failing to account for strings that contain no '1's or have fewer than three '1's.
error
Incorrectly calculating the number of valid splits by not considering all the possible ways to split the string.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if the string contains only '0's?
arrow_right_alt
How would you approach the problem if the string could contain other characters besides '0' and '1'?
arrow_right_alt
What optimizations can be made if we are allowed to split the string into more than three parts?

help

常见问题

外企场景

继续练习

#1513 仅含 1 的子串数 #1447 最简分数 #1759 统计同质子字符串的数目