Welcome to Subscribe On Youtube

1573. Number of Ways to Split a String

Description

Given a binary string s, you can split s into 3 non-empty strings s1, s2, and s3 where s1 + s2 + s3 = s.

Return the number of ways s can be split such that the number of ones is the same in s1, s2, and s3. Since the answer may be too large, return it modulo 109 + 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"

 

Constraints:

• 3 <= s.length <= 105
• s[i] is either '0' or '1'.

Solutions

• Java
• C++
• Python
• Go

• 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;
              }
          }
      }
  }
  

• class Solution {
  public:
      int numWays(string s) {
          int cnt = 0;
          for (char& c : s) {
              cnt += c == '1';
          }
          int m = cnt % 3;
          if (m) {
              return 0;
          }
          const int mod = 1e9 + 7;
          int n = s.size();
          if (cnt == 0) {
              return (n - 1LL) * (n - 2) / 2 % mod;
          }
          cnt /= 3;
          auto find = [&](int x) {
              int t = 0;
              for (int i = 0;; ++i) {
                  t += s[i] == '1';
                  if (t == x) {
                      return i;
                  }
              }
          };
          int i1 = find(cnt), i2 = find(cnt + 1);
          int j1 = find(cnt * 2), j2 = find(cnt * 2 + 1);
          return (1LL * (i2 - i1) * (j2 - j1)) % mod;
      }
  };
  

• 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
  }
  

All Problems

All Solutions