Problem statement

https://leetcode.com/problems/number-of-ways-to-split-a-string/

Solution

First we need to check if number of ones is divisibly by 3. If it is not, return False. Also, if it is equal to zero, we can use stars and bars problem to get direct answer. Finally we find places of all ones and we can put first split after the third part or ones and second after the second third of ones.

Complexity

Time complexity is O(n), space is O(n) as well. Space can be reduced to O(1).

Code

class Solution:
    def numWays(self, s):
        M = 10**9 + 7
        n, k = len(s), s.count("1")
        if k % 3 != 0: return 0
        if k == 0: return (n-1)*(n-2)//2 % M
        P = [i for i in range(n) if s[i] == "1"]
        return (P[k//3] - P[k//3 - 1]) * (P[2*k//3] - P[2*k//3 - 1]) % M