Minimum flips required in a binary string such that all K | Java program to find the minimum numbers of flips required in a binary string such that all substrings of size K has atleast one 1 ; Function to calculate and return the minimum number of flips to make string valid ; Stores the count of required flips ; Stores the last index of '1' in the string ; Check for the first substring of length K ; If i - th character is '1' ; If the substring had no '1' ; Increase the count of required flips ; Flip the last index of the window ; Update the last index which contains 1 ; Check for remaining substrings ; If last_idx does not belong to current window make it - 1 ; If the last character of the current substring is '1' , then update last_idx to i + k - 1 ; ; If last_idx == - 1 , then the current substring has no 1 ; Increase the count of flips ; Update the last index of the current window ; Store the last index of current window as the index of last '1' in the string ; Return the number of operations ; Driver Code
class GFG { public static int minimumMoves ( String s , int K ) { StringBuilder S = new StringBuilder ( s ) ; int N = S . length ( ) ; int ops = 0 ; int last_idx = - 1 ; for ( int i = 0 ; i < K ; i ++ ) { if ( S . charAt ( i ) == '1' ) last_idx = i ; } if ( last_idx == - 1 ) { ++ ops ; S . setCharAt ( K - 1 , '1' ) ; last_idx = K - 1 ; } for ( int i = 1 ; i < N - K + 1 ; i ++ ) { if ( last_idx < i ) last_idx = - 1 ; if ( S . charAt ( i + K - 1 ) == '1' ) last_idx = i + K - 1 ; if ( last_idx == - 1 ) { ++ ops ; S . setCharAt ( i + K - 1 , '1' ) ; last_idx = i + K - 1 ; } } return ops ; } public static void main ( String [ ] args ) { String S = "001010000" ; int K = 3 ; System . out . println ( minimumMoves ( S , K ) ) ; } }