LeetCode 1573. Number of Ways to Split a String Solution in Java, C++, Python & Go | Explanation + Code

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

Solution 1: Counting

First, we traverse the string s and count the number of characters 1, denoted as cnt. If cnt cannot be divided by 3, then it is impossible to split the string, so we directly return 0. If cnt is 0, it means there are no characters 1 in the string. We can choose any two positions out of n-1 positions to split the string into three substrings, so the number of ways is C_n-1^2.

If cnt \gt 0, we update cnt to ^cnt⁄₃, which is the number of characters 1 in each substring.

Next, we find the minimum index of the right boundary of the first substring, denoted as i₁, and the maximum index of the right boundary of the first substring (exclusive), denoted as i₂. Similarly, we find the minimum index of the right boundary of the second substring, denoted as j₁, and the maximum index of the right boundary of the second substring (exclusive), denoted as j₂. Then the number of ways is (i₂ - i₁) × (j₂ - j₁).

Note that the answer may be very large, so we need to take the modulo 10⁹+7.

The time complexity is O(n), and the space complexity is O(1). Here, n is the length of the string s.

Similar problems:

• 927. Three Equal Parts

PythonJavaC++Go

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)(code-box)

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; } } } }(code-box)

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; } };(code-box)

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 }(code-box)