simple solution c++ 35ms


  • 0
    S

    The idea is simple, we are only interested in 01 and 10 two cases and then use it to left and right expanding.

    class Solution {
    public:
        int countBinarySubstrings(string s) {
            //just check 01,10,0011,000111
            //search for 01 and 10 pattern and grow left and right, 
            int ans=0;
            int ind01=0,ind10=0;
            int n=s.size();
            int l,r;
            while(ind01!=string::npos|| ind10!=string::npos)
            {
                //cout<<ind01<<" "<<ind10<<":"<<ans<<endl;
                if(ind01!=string::npos)
                    ind01=s.find("01",ind01);
                if(ind01!=string::npos)
                {
                    ans++;
                    l=ind01-1;
                    r=ind01+2;
                    while(l>=0 && r<n && s[l--]=='0' && s[r++]=='1') ans++;
                    //cout<<"01:"<<ind01<<" "<<ans<<endl;
                    ind01+=2;
                    
                }
                if(ind10!=string::npos) 
                    ind10=s.find("10",ind10);
                if(ind10!=string::npos)
                {
                    ans++;
                    l=ind10-1;
                    r=ind10+2;
                    while(l>=0 && r<n && s[l--]=='1' && s[r++]=='0') ans++;
                    //cout<<"10:"<<ans<<endl;
                    ind10+=2;
                    
                }
    
            }
            return ans;
        }
    };
    

Log in to reply
 

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