Number of alternating substrings from a given Binary String | Function to count number of alternating substrings from a given binary string ; Initialize dp array , where dp [ i ] [ j ] stores the number of alternating strings starts with i and having j elements . ; Traverse the string from the end ; If i is equal to N - 1 ; Otherwise , ; Increment count of substrings starting at i and has 0 in the beginning ; Increment count of substrings starting at i and has 1 in the beginning ; Stores the result ; Iterate in the range [ 0 , N - 1 ] ; Update ans ; Return the ans ; Driver code ; Given Input ; Function call
def countAlternatingSubstrings ( S , N ) : NEW_LINE INDENT dp = [ [ 0 for i in range ( N ) ] for i in range ( 2 ) ] NEW_LINE for i in range ( N - 1 , - 1 , - 1 ) : NEW_LINE INDENT if ( i == N - 1 ) : NEW_LINE INDENT if ( S [ i ] == '1' ) : NEW_LINE INDENT dp [ 1 ] [ i ] = 1 NEW_LINE DEDENT else : NEW_LINE INDENT dp [ 0 ] [ i ] = 1 NEW_LINE DEDENT DEDENT else : NEW_LINE INDENT if ( S [ i ] == '0' ) : NEW_LINE INDENT dp [ 0 ] [ i ] = 1 + dp [ 1 ] [ i + 1 ] NEW_LINE DEDENT else : NEW_LINE INDENT dp [ 1 ] [ i ] = 1 + dp [ 0 ] [ i + 1 ] NEW_LINE DEDENT DEDENT DEDENT ans = 0 NEW_LINE for i in range ( N ) : NEW_LINE INDENT ans += max ( dp [ 0 ] [ i ] , dp [ 1 ] [ i ] ) NEW_LINE DEDENT return ans NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT S = "0010" NEW_LINE N = len ( S ) NEW_LINE print ( countAlternatingSubstrings ( S , N ) ) NEW_LINE DEDENT