1573. Number of Ways to Split a String.md

1573. Number of Ways to Split a String

---

the second one in Biweekly Contest 34.

---

Difficulty : Medium

Related Topics : String

---

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' or s[i] == '1'
• 3 <= s.length <= 10^5

---

Solution

• mine
  • Java
    • Runtime: 6 ms, faster than 71.43%, Memory Usage: 40.2 MB, less than 57.14% of Java online submissions

      //O(N)time
      //O(N)space
      public int numWays(String s) {
          int mod = 1000000007;
          char[] arr = s.toCharArray();
          int n = arr.length;
          List<Integer> list = new ArrayList<>();
          int count = 0;
          for(int i = 0; i < n; i++){
              if(arr[i] == '1') {
                  count++;
                  list.add(i);
              }
          }
          if(count % 3 != 0) return 0;
          if(count == 0) {
              long t =  (long)(n - 1) * (n - 2) / 2 % mod;
              return (int)t;
          }
          int each = count / 3;
          long f = list.get(each) - list.get(each - 1);
          long l = list.get(each * 2) - list.get(each * 2 - 1);
          return (int)(f * l % mod);
      }
      

---