Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1573.html
1573. Number of Ways to Split a String (Medium)
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
Related Topics:
String
Similar Questions:
Solution 1.
First count the number of 1s. The the count is not divisible by 3, we can’t split s into 3 parts, then return 0.
If cnt == 0, what we need to do is to choose 2 out of the N - 1 gaps between the N elements to split the s, so there are combination(N - 1, 2) = (N - 1) * (N - 2) / 2 cases.
Othewise, we need to find the number of possible cases of s1 and s3 respectively.
For s1, that’s the number of 0s between the cnt/3-th (1-based) and cnt/3 + 1-th 1 from the left side, plus 1. Let this be left.
For s3, that’s the number of 0s between the cnt/3-th (1-based) and cnt/3 + 1-th 1 from the right side, plus 1. Let this be right.
And the answer is different combinations of left and right and thus is left * right.
// OJ: https://leetcode.com/problems/number-of-ways-to-split-a-string/
// Time: O(N)
// Space: O(1)
class Solution {
public:
int numWays(string s) {
long mod = 1e9+7, cnt = 0;
for (char c : s) cnt += c == '1'; // cnt is the count of all 1s
if (cnt % 3) return 0; // if cnt is not divisible by 3, we can't split the string into 3 parts, return 0
if (cnt == 0) return (long)(s.size() - 1) * (s.size() - 2) / 2 % mod; // if cnt is 0, there are (N - 1) * (N - 2) / 2 cases.
int i = 0, c = 0, left = 0, right = 0; // left and right are the numbers of possible cases for s1 and s2 respectively
while (c <= cnt / 3) {
c += s[i++] == '1';
if (c == cnt / 3) ++left;
}
i = s.size() - 1, c = 0;
while (c <= cnt / 3) {
c += s[i--] == '1';
if (c == cnt / 3) ++right;
}
return (long)left * right % mod; // The answer is simply left * right
}
};
-
class Solution { public int numWays(String s) { final int MODULO = 1000000007; List<Integer> ones = new ArrayList<Integer>(); int length = s.length(); for (int i = 0; i < length; i++) { if (s.charAt(i) == '1') ones.add(i); } int size = ones.size(); if (size % 3 != 0) return 0; if (size == 0) { long ways = (long) (length - 1) * (length - 2) / 2; return (int) (ways % MODULO); } else { int index1 = size / 3, index2 = size / 3 * 2; int count1 = ones.get(index1) - ones.get(index1 - 1); int count2 = ones.get(index2) - ones.get(index2 - 1); long ways = (long) count1 * count2; return (int) (ways % MODULO); } } } ############ class Solution { private String s; public int numWays(String s) { this.s = s; int cnt = 0; int n = s.length(); for (int i = 0; i < n; ++i) { if (s.charAt(i) == '1') { ++cnt; } } int m = cnt % 3; if (m != 0) { return 0; } final int mod = (int) 1e9 + 7; if (cnt == 0) { return (int) (((n - 1L) * (n - 2) / 2) % mod); } cnt /= 3; long i1 = find(cnt), i2 = find(cnt + 1); long j1 = find(cnt * 2), j2 = find(cnt * 2 + 1); return (int) ((i2 - i1) * (j2 - j1) % mod); } private int find(int x) { int t = 0; for (int i = 0;; ++i) { t += s.charAt(i) == '1' ? 1 : 0; if (t == x) { return i; } } } } -
// OJ: https://leetcode.com/problems/number-of-ways-to-split-a-string/ // Time: O(N) // Space: O(1) class Solution { public: int numWays(string s) { long mod = 1e9+7, cnt = 0; for (char c : s) cnt += c == '1'; // cnt is the count of all 1s if (cnt % 3) return 0; // if cnt is not divisible by 3, we can't split the string into 3 parts, return 0 if (cnt == 0) return (long)(s.size() - 1) * (s.size() - 2) / 2 % mod; // if cnt is 0, there are (N - 1) * (N - 2) / 2 cases. int i = 0, c = 0, left = 0, right = 0; // left and right are the numbers of possible cases for s1 and s2 respectively while (c <= cnt / 3) { c += s[i++] == '1'; if (c == cnt / 3) ++left; } i = s.size() - 1, c = 0; while (c <= cnt / 3) { c += s[i--] == '1'; if (c == cnt / 3) ++right; } return (long)left * right % mod; // The answer is simply left * right } }; -
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) -
func numWays(s string) int { cnt := 0 for _, c := range s { if c == '1' { cnt++ } } m := cnt % 3 if m != 0 { return 0 } const mod = 1e9 + 7 n := len(s) if cnt == 0 { return (n - 1) * (n - 2) / 2 % mod } cnt /= 3 find := func(x int) int { t := 0 for i := 0; ; i++ { if s[i] == '1' { t++ if t == x { return i } } } } i1, i2 := find(cnt), find(cnt+1) j1, j2 := find(cnt*2), find(cnt*2+1) return (i2 - i1) * (j2 - j1) % mod }