1573. Number of Ways to Split a String

题目信息

题号:

1573

难度:

Medium

主题:

二进制字符串、组合计数、前缀

原题:

LeetCode 1573

重点:

把整个字符串切成三个非空连续部分,三部分中字符 1 的数量必须相等;答案取模

题目重述

给定二进制字符串 s。选择两个不同切分位置,把它按原顺序分成三个非空连续子串。

若三个子串包含的字符 1 数量相同,则该切分方案有效。请返回有效方案数量对 10^9 + 7 取模后的结果。

3 <= s.length <= 10^5。

自建示例

相邻目标一之间的零会增加切分选择:

输入:s = "10101"
输出:4
解释:三个一应分别落入三段,两处一之间各有两个合法切分位置,共 2*2=4 种。

字符串全为零时任意两个切分位置都有效:

输入:s = "0000"
输出:3
解释:从三个字符间隙中选择两个,共有三种方案。