1573. Number of Ways to Split a String LeetCode Solution
In this guide, you will get 1573. Number of Ways to Split a String LeetCode Solution with the best time and space complexity. The solution to Number of Ways to Split a String problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Number of Ways to Split a String
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'.
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(1)
1573. Number of Ways to Split a String LeetCode Solution in C++
class Solution {
public:
int numWays(string s) {
constexpr int kMod = 1'000'000'007;
const int ones = ranges::count(s, '1');
if (ones % 3 != 0)
return 0;
if (ones == 0) {
const long n = s.size();
return (n - 1) * (n - 2) / 2 % kMod;
}
int s1End = -1;
int s2Start = -1;
int s2End = -1;
int s3Start = -1;
int onesSoFar = 0;
for (int i = 0; i < s.length(); ++i) {
if (s[i] == '1')
++onesSoFar;
if (s1End == -1 && onesSoFar == ones / 3)
s1End = i;
else if (s2Start == -1 && onesSoFar == ones / 3 + 1)
s2Start = i;
if (s2End == -1 && onesSoFar == ones / 3 * 2)
s2End = i;
else if (s3Start == -1 && onesSoFar == ones / 3 * 2 + 1)
s3Start = i;
}
return static_cast<long>(s2Start - s1End) * (s3Start - s2End) % kMod;
}
}; /* code provided by PROGIEZ */
1573. Number of Ways to Split a String LeetCode Solution in Java
class Solution {
public int numWays(String s) {
final int kMod = 1_000_000_007;
final int ones = (int) s.chars().filter(c -> c == '1').count();
if (ones % 3 != 0)
return 0;
if (ones == 0) {
final long n = s.length();
return (int) ((n - 1) * (n - 2) / 2 % kMod);
}
int s1End = -1;
int s2Start = -1;
int s2End = -1;
int s3Start = -1;
int onesSoFar = 0;
for (int i = 0; i < s.length(); ++i) {
if (s.charAt(i) == '1')
++onesSoFar;
if (s1End == -1 && onesSoFar == ones / 3)
s1End = i;
else if (s2Start == -1 && onesSoFar == ones / 3 + 1)
s2Start = i;
if (s2End == -1 && onesSoFar == ones / 3 * 2)
s2End = i;
else if (s3Start == -1 && onesSoFar == ones / 3 * 2 + 1)
s3Start = i;
}
return (int) ((long) (s2Start - s1End) * (s3Start - s2End) % kMod);
}
} // code provided by PROGIEZ
1573. Number of Ways to Split a String LeetCode Solution in Python
class Solution:
def numWays(self, s: str) -> int:
kMod = 1_000_000_007
ones = s.count('1')
if ones % 3 != 0:
return 0
if ones == 0:
n = len(s)
return (n - 1) * (n - 2) // 2 % kMod
s1End = -1
s2Start = -1
s2End = -1
s3Start = -1
onesSoFar = 0
for i, c in enumerate(s):
if c == '1':
onesSoFar += 1
if s1End == -1 and onesSoFar == ones // 3:
s1End = i
elif s2Start == -1 and onesSoFar == ones // 3 + 1:
s2Start = i
if s2End == -1 and onesSoFar == ones // 3 * 2:
s2End = i
elif s3Start == -1 and onesSoFar == ones // 3 * 2 + 1:
s3Start = i
return (s2Start - s1End) * (s3Start - s2End) % kMod # code by PROGIEZ
