Number of alternating substrings from a given Binary String | c ++ program for the above approach ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int countAlternatingSubstrings ( string S , int N ) { vector < vector < int > > dp ( 2 , vector < int > ( N , 0 ) ) ; for ( int i = N - 1 ; i >= 0 ; i -- ) { if ( i == N - 1 ) { if ( S [ i ] == '1' ) dp [ 1 ] [ i ] = 1 ; else dp [ 0 ] [ i ] = 1 ; } else { if ( S [ i ] == '0' ) dp [ 0 ] [ i ] = 1 + dp [ 1 ] [ i + 1 ] ; else dp [ 1 ] [ i ] = 1 + dp [ 0 ] [ i + 1 ] ; } } int ans = 0 ; for ( int i = 0 ; i < N ; i ++ ) { ans += max ( dp [ 0 ] [ i ] , dp [ 1 ] [ i ] ) ; } return ans ; } int main ( ) { string S = "0010" ; int N = S . length ( ) ; cout << countAlternatingSubstrings ( S , N ) ; return 0 ; }