Number of Ways to Split a String — LeetCode 1573 Python Solution

The problem

Given a binary string s, you can split s into 3 non-empty strings s1, s2, and s3 where s1 + s2 + s3 = s. Return the number of ways s can be split such that the number of ones is the same in s1, s2, and s3.

Example

Input

s = "10101"

Output

4

Explanation

There are four ways to split s in 3 parts where each part contain the same number of letters '1'.

Python solution

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)

Complexity

Pattern: Math and Number Theory

Find the closed form, the invariant, or the modular identity — and skip the loop entirely. LeetCode 1573. Number of Ways to Split a String is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Math.

The math and number theory guide has the Python template for the pattern and the 485 LeetCode problems that use it.

Related problems