LeetCode Daily Question (1573. 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’.

整体分成 3 种情况：

1. 全是 0 的情况
2. 1 The number cannot be used 3 整除的情况
3. 1 The number can be used 3 整除的情况

情况 2 很简单,直接返回 0 即可.

情况 1 We are actually equivalent to putting 2 partitions to any 2 个槽里, We think of a slot between two numbers, 比如"0000"就有 3 个槽, When we put the first baffle in slot[i]里面的时候, Our second baffle can be placed onThe total number of slots-i-1in a slot, 注意 i 从 0 开始, So we just need to add up the number of options, 时间复杂度 O(n)

情况 2 In fact, what we are looking for is between the three groups 0 的数量, 比如"10100101000101", 我们可以把它拆解为 101|00|101|000|101, 每组含有 1 Both ends of the group must be 1, That is, the smallest group that meets the requirements of the question, 这其中的 00 和 000, 与两边的 1 The combination is made respectively 1001, 10001, We can place baffles on any of these slots, The separated groups must meet the subject criteria, 1001 有 3 个槽, 10001 有 4 个槽, So our actual choice has 3 * 4 = 12 种

impl Solution {
    
    pub fn num_ways(s: String) -> i32 {
    
        let one_num = s.chars().filter(|v| v == &'1').count();
        if one_num % 3 != 0 {
    
            return 0;
        }
        let mut ans = 0i64;
        if one_num == 0 {
    
            let slot_num = s.len() - 1;
            for i in 0..slot_num {
    
                ans += slot_num as i64 - i as i64 - 1;
            }
            return (ans % (10i64.pow(9) + 7)) as i32;
        }
        let mut zero_span1 = 0;
        let mut zero_span2 = 0;
        let mut prev_one_index = -1;
        let mut ones = 0;

        for (i, c) in s.chars().enumerate() {
    
            if c == '1' {
    
                ones += 1;
                if ones == one_num / 3 + 1 {
    
                    if prev_one_index == -1 {
    
                        zero_span1 = i as i64 + 1;
                    } else {
    
                        zero_span1 = i as i64 - prev_one_index;
                    }
                } else if ones == one_num / 3 * 2 + 1 {
    
                    if prev_one_index == -1 {
    
                        zero_span2 = i as i64 + 1;
                    } else {
    
                        zero_span2 = i as i64 - prev_one_index;
                    }
                    break;
                }
                prev_one_index = i as i64;
            }
        }
        (zero_span1 * zero_span2 % (10i64.pow(9) + 7)) as i32
    }
}