Leetcode 1678 Solution
This article provides solution to leetcode question 1678 (number-of-ways-to-split-a-string)
Access this page by simply typing in "lcs 1678" in your browser address bar if you have bunnylol configured.
Leetcode Question Link
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