LeetCode 696. Count Binary Substrings

[quinnwencn]

Description

Given a binary string s, return the number of non-empty substrings that have the same number of 0's and 1's, and all the 0's and all the 1's in these substrings are grouped consecutively.

Substrings that occur multiple times are counted the number of times they occur.

Example 1:

Input: s = "00110011"
Output: 6
Explanation: There are 6 substrings that have equal number of consecutive 1's and 0's: "0011", "01", "1100", "10", "0011", and "01".
Notice that some of these substrings repeat and are counted the number of times they occur.
Also, "00110011" is not a valid substring because all the 0's (and 1's) are not grouped together.
Example 2:

Input: s = "10101"
Output: 4
Explanation: There are 4 substrings: "10", "01", "10", "01" that have equal number of consecutive 1's and 0's.

Constraints:

1 <= s.length <= 105
s[i] is either '0' or '1'.

[quinnwencn]

Analysis

First, I try to solve this problem by enumeration:

class Solution {
public:
    int countBinarySubstrings(string s) {
        int count { 0 };
        for (auto i = 0; i < s.length(); ++i) {
            auto r = i;
            int refCount = 0;
            while (r < s.length() && s[r] == s[i]) {
                refCount++;
                r++;
            }

            auto rr = r;
            while (rr < s.length() && s[rr] == s[r]) {
                refCount--;
                if (refCount == 0) {
                    break;
                }
                rr++;
            }
            if (refCount == 0) {
                count++;
            }
        }

        return count;
    }
};

But this won't pass all the test cases. Leetcode tells me that Time limit exceeded. The time complexity of the solution is O(N^2).
Since the result of 0011 is 2, which is the same as 00011 and 00111. That means only the minimum number of 1 or 0 matters in a combination. So here is the new solution, the time complexity of which is O(N).

class Solution {
public:
    int countBinarySubstrings(string s) {
        int count { 0 };
        int zeros {0};
        int ones {0};
        bool finishZero {false};
        bool finishOne {false};
        for (auto i = 0; i < s.length(); ++i) {
            if (s[i] == '0') {
                zeros++;
                finishOne = true;
                if (s[i + 1] == '1' && finishZero) {
                    count += std::min(ones, zeros);
                    ones = 0;
                    finishZero = false;
                }
            }

            if (s[i] == '1') {
                ones++;
                finishZero = true;
                if (s[i + 1] == '0' && finishOne) {
                    count += std::min(ones, zeros);
                    zeros = 0;
                    finishOne = false;
                }
            }
        }

        count += std::min(zeros, ones);

        return count;
    }
};

[quinnwencn]

https://review.gerrithub.io/c/robertwenhk/program-record/+/1194690