Number of alternating substrings from a given Binary String | Java 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
import java . util . * ; class GFG { static int countAlternatingSubstrings ( String S , int N ) { int [ ] [ ] dp = new int [ 2 ] [ N ] ; for ( int i = 0 ; i < 2 ; i ++ ) { for ( int j = 0 ; j < N ; j ++ ) { dp [ i ] [ j ] = 0 ; } } for ( int i = N - 1 ; i >= 0 ; i -- ) { if ( i == N - 1 ) { if ( S . charAt ( i ) == '1' ) dp [ 1 ] [ i ] = 1 ; else dp [ 0 ] [ i ] = 1 ; } else { if ( S . charAt ( 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 += Math . max ( dp [ 0 ] [ i ] , dp [ 1 ] [ i ] ) ; } return ans ; } public static void main ( String [ ] args ) { String S = "0010" ; int N = S . length ( ) ; System . out . print ( countAlternatingSubstrings ( S , N ) ) ; } }