# 1573. Number of Ways to Split a String
###### tags: `Leetcode` `Medium` `HashMap` `Permutations`
Link: https://leetcode.com/problems/number-of-ways-to-split-a-string/
## 思路
1. if (n < 3) return 0;
2. if cnt of 1s is not dividable by 3, return 0;
3. **(special case)** if no 1s, you may select any 2 slots btwn 0s to divide, just return num of combinations, 从n-1个可以cut的地方选两个出来; $\tbinom{n-1}{2}$ 
4. otherwise, 找到$prefixsum = \frac{totalsum}{3}$的区域，例如长度为$l_1$, 再找到$prefixsum = 2*\frac{totalsum}{3}$ , 长度为$l_2$，那么可以插入cut的地方就有$(l_1+1)*(l_2+1)$个
## Code

class Solution {
    public int numWays(String s) {
        long res = 0, n = s.length(), mod = 1000000007, cntOnes = 0;
        if (n < 3) return 0;
        for (int i = 0; i < n; i++) if (s.charAt(i) == '1') cntOnes++;
        if (cntOnes % 3 != 0) return 0;
        if (cntOnes == 0) return (int) ((n - 1) * (n - 2) / 2 % mod); // combinations, select 2 slots from n - 1 slots;
        long firstZeros = 0, secondZeros = 0, prefixOnes = 0;
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if (c == '1') prefixOnes++;
            else {
                if (prefixOnes == cntOnes / 3) firstZeros++;
                else if (prefixOnes == cntOnes / 3 * 2) secondZeros++;
            }
        }
        return (int) (++firstZeros * ++secondZeros % mod);  // two 0s form 3 slots
    }
}