C++ O(n) Time O(1) Space with easy explanation


  • 0
    V

    Count the number of each group.
    for each 0/1 group size == n, it can produce n different subarrays.
    for example:
    000111 => 000111, 0011, 01
    The tricky part is that the latter 1's group might also produce more different subarrays.
    1's group size = 3, 0's group size = 4 for example:
    1110000 => 111000, 1100, 10
    which is min(1's group size, 0's group size)

    '''
    class Solution {
    public:
    int countBinarySubstrings(string str) {

        int ans = 0;
        int preCounts = 0;
    
        for (int i = 0; i < str.size(); ) {
            
            int b, e;
            
            b = i;
            e = i;
            while (++e < str.size() && str[b] == str[e]);
            
            int counts = e - b;            
            ans += min(preCounts, counts);
            
            preCounts = counts;
            i += counts;
            
        }
            
        return ans;
        
    }
    

    };
    '''


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.