Leetcode 1573: Number of Ways to Split a String
Given a binary string, you need to split it into three non-empty parts such that each part contains the same number of ‘1’s. You must return the total number of ways to split the string, with the result modulo 10^9 + 7.
Problem
Approach
Steps
Complexity
Input: The input is a binary string, meaning it contains only '0's and '1's.
Example: Input: s = "110101"
Constraints:
• 3 <= s.length <= 10^5
• Each character in s is either '0' or '1'.
Output: The output should be the number of ways to split the binary string into three parts where each part has the same number of '1's. The result should be returned modulo 10^9 + 7.
Example: Output: 3
Constraints:
Goal: The goal is to count how many ways we can split the string into three parts such that each part has the same number of '1's.
Steps:
• First, count the total number of '1's in the string.
• If the total number of '1's is not divisible by 3, return 0 since it's not possible to split them evenly.
• Divide the total number of '1's by 3 to find the number of '1's each part should contain.
• Track the possible positions where the first and second cuts can be made to split the string into three parts with an equal number of '1's.
Goal: The binary string has a length of at least 3 and at most 10^5 characters.
Steps:
• The string must have at least 3 characters.
• The string must contain only '0's and '1's.
Assumptions:
• The string is guaranteed to contain only '0's and '1's.
• The total number of '1's in the string is divisible by 3 for a valid split.
• Input: Example 1: s = "110101"
• Explanation: The string has 4 '1's, so each part must have 4 / 3 = 1 '1'. The valid splits are: "1|1|01", "1|10|1", and "11|0|1".
• Input: Example 2: s = "1001"
• Explanation: The string has 2 '1's, which is not divisible by 3, so there are no valid ways to split the string.
• Input: Example 3: s = "0000"
• Explanation: The string has 0 '1's, so any valid split would be a valid solution, and the number of splits is 3.
Approach: The problem involves counting how many ways we can split the string into three parts such that each part contains the same number of '1's. We first calculate the total number of '1's, check if it is divisible by 3, and then find positions to make the cuts.
Observations:
• The total number of '1's must be divisible by 3 for an equal split.
• We can use the positions of '1's to count the valid splits.
• By counting the number of '1's and tracking the positions where each cut can occur, we can efficiently calculate the number of valid splits.
Steps:
• Count the total number of '1's in the string.
• If the total is not divisible by 3, return 0.
• Divide the total '1's by 3 to get the number of '1's each part should contain.
• Use two passes through the string to count the number of valid first and second cut positions.
• Multiply the counts for the first and second cuts to get the total number of valid splits.
Empty Inputs:
• The string will always have at least 3 characters.
Large Inputs:
• The algorithm should efficiently handle strings with lengths up to 10^5.
Special Values:
• Strings with all '0's have multiple valid splits.
Constraints:
• Ensure that the solution handles the maximum input size efficiently.
int numWays(string s) {
long n = s.size();
int one = 0;
for(char x: s)
one += (x == '0')? 0: 1;
int mod = (int) 1e9 + 7;
if(one == 0) return (int)((n - 2) * (n - 1) / 2 % mod);
if(one % 3 != 0) return 0;
long long waysOfFirstCut = 0, waysOfSecondCut = 0;
int net = one / 3, tmp = 0;
for(int i = 0; i < n; i++) {
if(s[i] == '1') tmp++;
if(tmp == net) waysOfFirstCut++;
else if(tmp == 2 * net) waysOfSecondCut++;
}
return (int)(waysOfFirstCut *waysOfSecondCut % mod) ;
}
1 : Function Definition
int numWays(string s) {
Defines the function `numWays` which takes a string `s` as input and returns an integer representing the number of ways to divide the string into three parts with equal '1's.
2 : Size Calculation
long n = s.size();
Calculates the size of the string `s` and stores it in `n`.
3 : Count '1's
int one = 0;
Initializes a counter variable `one` to count the number of '1's in the string `s`.
4 : Loop Through String
for(char x: s)
Starts a loop to iterate through each character `x` in the string `s`.
5 : Count '1's in String
one += (x == '0')? 0: 1;
Increments the counter `one` for each '1' encountered in the string `s`.
6 : Modulo Definition
int mod = (int) 1e9 + 7;
Defines the modulus value `mod` as 1e9 + 7 to avoid overflow and ensure the result fits within the limits.
7 : Edge Case for Zero '1's
if(one == 0) return (int)((n - 2) * (n - 1) / 2 % mod);
Handles the edge case where there are no '1's in the string. In this case, the number of ways to divide the string into three equal parts is calculated using the formula (n-2)*(n-1)/2.
8 : Check for Divisibility by 3
if(one % 3 != 0) return 0;
Checks if the total number of '1's is divisible by 3. If not, it's impossible to divide the string into three equal parts, so it returns 0.
9 : Cut Variables Initialization
long long waysOfFirstCut = 0, waysOfSecondCut = 0;
Initializes two variables `waysOfFirstCut` and `waysOfSecondCut` to keep track of the possible positions for the first and second cuts.
10 : Net Calculation
int net = one / 3, tmp = 0;
Calculates `net`, the number of '1's in each part of the string (one-third of the total number of '1's), and initializes `tmp` to count the '1's encountered while iterating through the string.
11 : Loop Through String Again
for(int i = 0; i < n; i++) {
Starts a loop to iterate through the string `s` again to find the positions where the cuts can be made.
12 : Count '1's During Iteration
if(s[i] == '1') tmp++;
Increments the counter `tmp` whenever a '1' is encountered during the iteration.
13 : First Cut Count
if(tmp == net) waysOfFirstCut++;
If the counter `tmp` reaches `net`, it means the first cut can be made, so `waysOfFirstCut` is incremented.
14 : Second Cut Count
else if(tmp == 2 * net) waysOfSecondCut++;
If the counter `tmp` reaches `2 * net`, it means the second cut can be made, so `waysOfSecondCut` is incremented.
15 : Return Result
return (int)(waysOfFirstCut * waysOfSecondCut % mod);
Calculates the total number of ways to divide the string into three equal parts by multiplying the number of ways to make the first and second cuts. The result is taken modulo `mod`.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is O(n) due to the need to iterate over the string to count the '1's and find valid split positions.
Best Case: O(1)
Worst Case: O(1)
Description: The space complexity is O(1) since only a few variables are used to track the counts and positions.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus