[696. Count Binary Substrings] C++ O(n) AC


  • 0
    class Solution {
    public:
    int countBinarySubstrings(string s) {
        if(s.size() < 2) return 0;
        int res = 0;
        pair<int,int> p;
        if(s[0] == '1'){
            p = {0,1};
        }else{
            p = {1,0};
        }
        for(int i = 1; i < s.size(); ++i){
            if(s[i] == s[i-1]){
                if(s[i] == '1'){
                    p.second++;
                    p.first = max(0, p.first - 1);
                }else{
                    p.first++;
                    p.second = max(0, p.second - 1);
                }
            }else{
                if(s[i] == '1'){
                    p.second = 1;
                }else{
                    p.first = 1;
                }
            }
            res += min(p.first, p.second) == 0 ? 0 : 1;
        }
        return res;
    }
    };

Log in to reply
 

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