Given a binary string s (a string consisting only of ‘0’s and ‘1’s), we can split s into 3 non-empty strings s1, s2, s3 (s1+ s2+ s3 = s).
Return the number of ways s can be split such that the number of characters ‘1’ is the same in s1, s2, and s3.
Since the answer may be too large, return it modulo 10^9 + 7.
Example 1:
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'. "1|010|1" "1|01|01" "10|10|1" "10|1|01"
Example 2:
Input: s = "1001" Output: 0
Example 3:
Input: s = "0000" Output: 3 Explanation: There are three ways to split s in 3 parts. "0|0|00" "0|00|0" "00|0|0"
Example 4:
Input: s = "100100010100110" Output: 12
Constraints:
s[i] == '0'ors[i] == '1'3 <= s.length <= 10^5
Solution: Counting
Count how many ones in the binary string as T, if not a factor of 3, then there is no answer.
Count how many positions that have prefix sum of T/3 as l, and how many positions that have prefix sum of T/3*2 as r.
Ans = l * r
But we need to special handle the all zero cases, which equals to C(n-2, 2) = (n – 1) * (n – 2) / 2
Time complexity: O(n)
Space complexity: O(1)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
class Solution { public: int numWays(string s) { const int kMod = 1e9 + 7; const long n = s.length(); int t = 0; for (char c : s) t += c == '1'; if (t % 3) return 0; if (t == 0) return ((1 + (n - 2)) * (n - 2) / 2) % kMod; t /= 3; long l = 0; long r = 0; for (int i = 0, c = 0; i < n; ++i) { c += (s[i] == '1'); if (c == t) ++l; else if (c == t * 2) ++r; } return (l * r) % kMod; } }; |
Python3
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
class Solution: def numWays(self, s: str) -> int: n = len(s) t = s.count('1') if t % 3 != 0: return 0 if t == 0: return ((n - 1) * (n - 2) // 2) % (10**9 + 7) t //= 3 l, r, c = 0, 0, 0 for i, ch in enumerate(s): if ch == '1': c += 1 if c == t: l += 1 elif c == t * 2: r += 1 return (l * r) % (10**9 + 7) |
One pass: Space complexity: O(n)
Python3
|
1 2 3 4 5 6 7 8 9 10 11 |
class Solution: def numWays(self, s: str) -> int: n = len(s) p = defaultdict(int) c = 0 for ch in s: if ch == '1': c += 1 p[c] += 1 if c % 3 != 0: return 0 if c == 0: return ((n - 1) * (n - 2) // 2) % (10**9 + 7) return (p[c // 3] * p[c // 3 * 2]) % (10**9 + 7) |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
huahualeetcode
Be First to Comment