Challenge 0

'''
This program counts the number of substrings in s, which satisfies the following 2 constraints:
    1. 0's and 1's are grouped together (contiguous), and
    2. Number of 0's == Number of 1's

    Constraints: s is comprised of only 0's and 1's and 5 <= s <= 5x10^5

    eg:
        when s = '00110' num substrings = 3 (0011, 01, 10)
        when s = '10101' num substrings = 4 (10, 01, 10, 01)
        when s = '10001' num substrings = 2 (10, 01)
        when s = '0001100100011100' 
                         num substrings = 11 (01, 0011, 10, 1100, 01, 10, 01, 0011, 000111, 10, 1100)

'''

#import sys

def propagateAndCheck(s, p0, p1):
    cnt = 0
    while p0 > 0 and p1 < len(s) - 1:
        if s[p0 - 1] == s[p0] and s[p1 + 1] == s[p1]:
            cnt += 1
        else:
            break

        p0 -= 1
        p1 += 1

    return cnt


def findContSubstr(s):

    subStrCnt = 0

    for idx in xrange(1, len(s)):
        if s[idx - 1] != s[idx]:
            subStrCnt += 1 + propagateAndCheck(s, (idx - 1), idx)

    return subStrCnt

#///////////////////////////////////////////////
# The following does a one time traversal of 's',
# so complexity is O(n)
#///////////////////////////////////////////////
def findContSubstrOptimal(s):

    subStrCnt = 0
    cntChar0 = 1
    cntChar1 = 0

    for idx in xrange(1, len(s)):
        if s[idx - 1] != s[idx]:
            subStrCnt += 1
            if cntChar1 >= 1:
                # assign cntChar1 to cntChar0
                cntChar0 = cntChar1

            # whenever there is a mismatch start cntChar1
            cntChar1 = 1

        else:
            # this happens at the very beginning of string traversal
            # at the very beginning keep counting the number of same chars
            if cntChar1 == 0: 
                cntChar0 += 1
            else:
                cntChar1 += 1

                # Count all the other contiguous substrings, till cntChar1 becomes cntChar0
                if cntChar1 <= cntChar0:
                    subStrCnt += 1


    return subStrCnt


if __name__ == "__main__":
    print 'Enter raw string with 0s and 1s: ',
    s = raw_input().strip()
    print 'given s: ', s
    #contSubStr = findContSubstr(s)
    contSubStr = findContSubstrOptimal(s)
    print 'Num contiguous substr: ', contSubStr