Leetcode 1678 Solution

This article provides solution to leetcode question 1678 (number-of-ways-to-split-a-string)
Categories:
Tags:
Access this page by simply typing in "lcs 1678" in your browser address bar if you have bunnylol configured.

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

Solution

class Solution:
    def numWays(self, s: str) -> int:
        n = len(s)
        one_cnt = sum([1 for ch in s if ch == '1'])

        if one_cnt % 3 != 0:
            return 0

        if one_cnt == 0:
            return ((n - 1) * (n - 2) // 2) % 1000000007

        curr_cnt = 0
        last_one_pos = 0

        zero_cnts = []

        for i, ch in enumerate(s):
            if ch == '1':
                curr_cnt += 1

                if curr_cnt > one_cnt // 3:
                    curr_cnt = 1
                    zero_cnts.append((i - last_one_pos - 1))

                last_one_pos = i

        cnt1 = zero_cnts[0]
        cnt2 = zero_cnts[1]

        return (cnt1 + 1) * (cnt2 + 1) % 1000000007