Linear solution with constant memory.

  • 0

    The code is comented itself, but just to make it clear, this code runs in O(n) time, each iteration we move the right pointer forward anyway.

    Each time when we see a S[i - 1] != S[i], we need to count how many substrings with a center in S[i - 1] and S[i] have the left part equals to the right part, I mean, we just start to increase k ( = 0), while (S[i - k - 1] == S[i - 1]) and (S[i + k] == S[i]). Each time we increase k, we also increase the asnwer by 1.

    int countBinarySubstrings(string s) {
        int n = s.size();
        int ans = 0;
        int hi = 0;//high
        while(hi < n){
            int lo = hi - 1;//starting low
            bool hasAns = 0;
            char leftChar = s[lo], rightChar = s[hi];
            while(lo >= 0 && hi < n && s[lo] == leftChar && s[hi] == rightChar && leftChar != rightChar){
                //if we have an increasing substring so that the 
                //left part is equals to the right part, each substring must be added to the asnwer.
                hasAns = 1;
            if(!hasAns) hi++;//just move forward if left does't match with right.
        return ans;

    If you find I did something wrong, tell me.

Log in to reply

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