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 ; Given Input ; Function call
function countAlternatingSubstrings ( S , N ) { var dp = new Array ( 2 ) ; dp [ 0 ] = Array ( N ) . fill ( 0 ) ; dp [ 1 ] = Array ( N ) . fill ( 0 ) ; var i ; for ( i = N - 1 ; i >= 0 ; i -- ) { if ( i == N - 1 ) { if ( S [ i ] == ' ' ) dp [ 1 ] [ i ] = 1 ; else dp [ 0 ] [ i ] = 1 ; } else { if ( S [ i ] == ' ' ) dp [ 0 ] [ i ] = 1 + dp [ 1 ] [ i + 1 ] ; else dp [ 1 ] [ i ] = 1 + dp [ 0 ] [ i + 1 ] ; } } var ans = 0 ; for ( i = 0 ; i < N ; i ++ ) { ans += Math . max ( dp [ 0 ] [ i ] , dp [ 1 ] [ i ] ) ; } return ans ; } var S = " " ; var N = S . length ; document . write ( countAlternatingSubstrings ( S , N ) ) ;