1573. Number of Ways to Split a String

by

1573. Number of Ways to Split a String

Given a binary string s (a string consisting only of ‘0’s and ‘1’s), we can split s into 3 non-empty strings s1, s2, s3 (s1+ s2+ s3 = s).

Return the number of ways s can be split such that the number of characters ‘1’ is the same in s1, s2, and s3.

Since the answer may be too large, return it modulo 10^9 + 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"

Example 4:

Input: s = "100100010100110"
Output: 12

Constraints:

  • 3 <= s.length <= 10^5
  • s[i] is '0' or '1'.

思路

对于只有 0 的字符串，结果为 \(C^{2}_{s.length()}\)。

将 s 中的 1 的个数 count_1 除以三得到 count_in_one_str。从头开始数1，第一个分隔符的起始位置 start_i_1 为恰好数到 count_in_one_str 个 1 的 index 处（的右侧）；结束位置 end_i_1 为起始位置 start_i_1 后的下一个 1 的 index （不包含此位置）。第一个分隔符共有 end_i_1 – start_i_1 种位置可选。

第二个分隔符类似。

创建一个 cursor_flag 记录当前在寻找哪一个分隔符位置：0 表示在找 start_i_1，1 表示在找 end_i_1，….

每次找到一个分隔符位置后切换 cursor_flag。

需注意当 cursor_flag 从 1 切到 2 时，若 count_in_one_str 为 1，那么此 index 即为 end_i_1 也为 start_i_2。

class Solution {
public:
    int numWays(string s) {
        int count_1 = 0;
        for (auto ch: s) {
            if (ch == '1') {
                count_1++;
            }
        }
        if (count_1 % 3 != 0) return 0;
        
        if (count_1 == 0) {
            long long cnt1=s.length()-2;
            return (cnt1 * (cnt1 + 1) / 2) % 1000000007;
        }
        
        int count_in_one_str = count_1 / 3;
        count_1 = 0;
        long long start_i_1, end_i_1, start_i_2, end_i_2;
        int cursor_flag = 0;
        
        for (int i = 0; i < s.length(); ++i) {
            if (s[i] == '1') {
                count_1++;
                if (count_1 == count_in_one_str && cursor_flag == 0) {
                    start_i_1 = i;
                    cursor_flag = 1;
                    count_1 = 0;
                }
                else if (count_1 == count_in_one_str && cursor_flag == 2) {
                    start_i_2 = i;
                    cursor_flag = 3;
                    count_1 = 0;
                }
                else if (cursor_flag == 1) {
                    end_i_1 = i;
                    cursor_flag = 2;
                    if (count_1 == count_in_one_str) {
                        start_i_2 = i;
                        cursor_flag = 3;
                        count_1 = 0;
                    }
                }
                else if (cursor_flag == 3) {
                    end_i_2 = i;
                    break;
                }
            }
        }
        return (end_i_1 - start_i_1) * (end_i_2 - start_i_2) % 1000000007;
    }
};

Runtime: 28 ms, faster than 98.40% of C++ online submissions for Number of Ways to Split a String.

Memory Usage: 13.9 MB, less than 86.04% of C++ online submissions for Number of Ways to Split a String.

Leave a Comment