Maximum count of 0 s between two 1 s in given range for Q queries | Java program for the above approach ; Function to count the number of 0 s lying between the two 1 s for each query ; Stores count of 0 ' s ▁ that ▁ are ▁ ▁ right ▁ to ▁ the ▁ most ▁ recent ▁ 1' s ; Stores count of 0 ' s ▁ that ▁ are ▁ ▁ left ▁ to ▁ the ▁ most ▁ recent ▁ 1' s ; Stores the count of zeros in a prefix / suffix of array ; Stores the count of total 0 s ; Traverse the string S ; If current character is '1' ; Otherwise ; Update the rightBound [ i ] ; Update count and total to 0 ; Traverse the string S in reverse manner ; If current character is '1' ; Otherwise ; Update the leftBound [ i ] ; Traverse given query array ; Update the value of count ; Print the count as the result to the current query [ L , R ] ; Driver Code
import java . lang . * ; import java . util . * ; class GFG { static void countOsBetween1s ( String S , int N , int [ ] [ ] Q ) { int [ ] leftBound = new int [ N ] ; int [ ] rightBound = new int [ N ] ; int count = 0 ; int total = 0 ; for ( int i = 0 ; i < N ; i ++ ) { if ( S . charAt ( i ) == '1' ) { count = total ; } else if ( S . charAt ( i ) == '0' ) { total ++ ; } rightBound [ i ] = count ; } count = 0 ; total = 0 ; for ( int i = N - 1 ; i >= 0 ; i -- ) { if ( S . charAt ( i ) == '1' ) { count = total ; } else if ( S . charAt ( i ) == '0' ) { total ++ ; } leftBound [ i ] = count ; } for ( int q = 0 ; q < Q . length ; q ++ ) { int L = Q [ q ] [ 0 ] ; int R = Q [ q ] [ 1 ] ; count = leftBound [ L ] + rightBound [ R ] - total ; System . out . print ( count + " ▁ " ) ; } } public static void main ( String [ ] args ) { String S = "1001010" ; int Q [ ] [ ] = { { 0 , 4 } , { 0 , 5 } } ; int N = S . length ( ) ; countOsBetween1s ( S , N , Q ) ; } }