6-liner O(N) time and O(1) space


  • 0

    Let L_1, L_2, ... L_k be the lengths of consecutive digit substrings, the answer to this problem is simply

    res = min(L_1, L2) + min(L_2, L_3) + ... + min(L_(k-1), L_k).

        int countBinarySubstrings(string s) {
            int res = 0;
            for (int i = 0, preL = 0, curL = 0; i < s.size(); ++i) 
            {
                if (i && s[i] == s[i-1]) ++curL;
                else preL = curL, curL = 1;
                if (curL <= preL) res++;
            }
            return res; 
        }
    

Log in to reply
 

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