Minimize Flips to Make the Binary String as all 1s by Flipping Characters in a Substring of size K Repeatedly

Aman kumar Chourasiya
Last Updated: Jul 3, 2022
Difficulty Level :
MEDIUM

Introduction

In this blog, we will discuss a problem based on strings. Strings are a widely asked topic in coding contests among Data Structures and technical interviews. Greedy is an algorithmic paradigm that develops a solution piece by piece, always opting for the next piece that provides the most evident and immediate benefit. We will be using the greedy approach to solve this problem. 

Problem Statement

Ninja has given you a binary string, ‘S’, and an integer, ‘K’. Your task is to find the minimum number of operations required to make all characters 1s in the string, ‘S’. In one operation you can flip all the characters of any substring of size ‘K’. If it is not possible to make all characters as 1s, then print -1.

Binary String: A binary string is a string that contains only ‘0’ or ‘1’ as characters.

Example

‘00101’, ‘10101’, ‘1111’, ‘0000’ etc.

Input

00010110 3

Output

3

Explanation

We can convert the given string into all 1s in 3 operations. Operations performed are:

  1. Flip S[0, 2]  (string becomes ‘11110110’).
  2. Flip S[4, 6]  (string becomes ‘11111000’).
  3. Flip S[5, 7]  (string becomes ‘11111111’). 

Approach

We can approach the given coding challenge in a greedy way. Let us focus on any one index in the given binary string, say, IND such that ‘S[IND]’ = ‘0’. We can consider substrings of size ‘K’ containing this index ‘IND’ and flip these substrings to change the character at ‘S[IND]’. The greedy logic is we can maintain a prefix of all 1’s and a suffix containing a mix of 0’s and 1’s yet to be addressed. We iterate from 0 to N - 1 using the variable ‘IND’. If ‘S[IND]’ = ‘0’, we can flip the next K characters starting from ‘IND’. 

This is the only possible solution to flip the character at index ‘IND’. It is because all the substrings with ‘IND’ being the non-first character are already addressed in previous iterations. All those flips before finally ended up with ‘S[IND]’ being ‘0’. Thus the only possible substring left to be considered is the one starting with IND itself.

Algorithm

1. Declare a variable ‘MIN_OPERATIONS’ to store the minimum number of operations required.

2. Iterate over the string ‘S’ and do the following:

a. If S[i] is ‘0’ and there is a substring of length at least ‘K’ present in the right (i.e., i + K <= N), then flip all the characters in the substring S[i, i + K].

b. Increment ‘MIN_OPERATIONS’ as we just performed a flip operation.

3. Then, once again, iterate over the string ‘S’ and check if any character ‘0’ is present in the string. 

4. If ‘0’ is not present in the modified string, print ‘MIN_OPERATIONS’; otherwise, print -1.

Ilustration Minimum Flips

Implementation in C++

#include <iostream>
using namespace std;
int findMinOperations(string S, int K){

    /* Storing the length of Input string */
    int N = S.length();

    /* To store the minimum number of operations required. */
    int minOperations = 0;

    /* Iterating over the string S. */
    for(int ind=0; ind<N; ind++){

        /* If ith character is '0' and there is substring of length K
        present on the right side. */
        if(!(S[ind] - '0') && ind+K <= N){
           
            /* Then flip the substring s[i, i+k]. */
            for(int j=ind; j<ind+K; j++){

                if(S[j]-'0') S[j] = '0';
                else S[j] = '1';
            }

            /* Incrementing the answer since we performed a flip. */
            minOperations++;
        }
    }

    bool zeroPresent = false;

    /* Checking if the string still contains a zero. */
    for(int i=0; i<N; i++){
        if(S[i] == '0')zeroPresent = true;
    }

    /* If there still exists a zero then return -1 otherwise return
    minimum number of operations required. */
    return (zeroPresent ? -1 : minOperations);
}

// Driver function.
int main(){
    string S; cin >> S;
    int K; cin >> K;

    int ans = findMinOperations(S, K);

    cout << "Minimum operations required are : ";
    cout << ans << "\n\n";
    return 0;
}

Input

00010110 3

Output

Minimum operations required are : 3

Program in Python 

def minOperations(Str, K, N):
   S = list(Str)
   # Stores the count of minimum no. of
   # operations needed
   min = 0

   i = 0

   # Traversing the string S
   for i in range(0, N):

       # If the character in S is 0
       if (S[i] == '0' and i + K <= N):

           # flipping the substrings of
           # size K starting from index i
           j = i
           while(j < i + K):
               if (S[j] == '1'):
                   S[j] = '0'
               else:
                   S[j] = '1'
               j += 1

           # Increment the minimum
           #count of operations
           min += 1

   # check if string S contains any 0s
   temp = 0

   for i in range(0, N):
       temp += 1
       if (S[i] == '0'):
           break

   # If string S contains only 1's
   if (temp == N):
       return min
   else:
       return -1

# Driver Code begins
S = "00010110"
N = len(S) #length of string S
K = 3
ans=minOperations(S, K, N)
print("Minimum operations required are :",ans)

Output

Minimum operations required are : 3

Program in Java


import java.util.Scanner;

public class Minflips {
    static int findMinOperations(char S[], int K){

        /* Storing the length of Input string */
        int N = S.length;
    
        /* To store the minimum number of operations required. */
        int minOperations = 0;
    
        /* Iterating over the string S. */
        for(int ind=0; ind<N; ind++){
    
            /* If ith character is '0' and there is substring of length K
            present on the right side. */
            int check=(S[ind] - '0');
            if((check == 0) && (ind+K <= N)){
               
                /* Then flip the substring s[i, i+k]. */
                for(int j=ind; j<ind+K; j++){
                    int check_again=(S[j]-'0');
                    if(check_again>0){
                        S[j] = '0';
                    } 
                    else{
                        S[j] = '1';
                    }
                }
    
                /* Incrementing the answer since we performed a flip. */
                minOperations++;
            }
        }
    
        boolean zeroPresent = false;
    
        /* Checking if the string still contains a zero. */
        for(int i=0; i<N; i++){
            if(S[i] == '0')zeroPresent = true;
        }
    
        /* If there still exists a zero then return -1 otherwise return
        minimum number of operations required. */
        return (zeroPresent ? -1 : minOperations);
    }
    
    
    public static void main(String[] args) {
        try (Scanner sc = new Scanner(System.in)) {
            char[] str= sc.next().toCharArray();   
            int K=sc.nextInt();  
            // Call function.
            int ans = findMinOperations(str, K);

            System.out.print("Minimum operations required are : ");
            // Print the final answer.
            System.out.print(ans); 
            System.out.println(); 
            System.out.println(); 
        }
    }
}

Input

00010110 3

Output

Minimum operations required are : 3

Complexity Analysis

Time Complexity

The time complexity of the above approach is O(N * K), where ‘N’ is the size of the binary string and ‘K’ is the input parameter.

It is because we are using two nested for loops with ‘N’ and ‘K’ as limits.

Space Complexity

The auxiliary space complexity of the above approach is O(1).

As we are using constant space to execute the algorithm.

Frequently Asked Questions

What is the time complexity for the solution to this problem?

The time complexity for the above solution is O(N*K) where N is the size of the string and K is the length of the string that can be flipped at a time

For what value of K will we always get an answer?

If K = 0 then we always get an answer as only a single character has to be flipped every time.

Conclusion

We used a greedy approach in this blog to solve the problem. We solved this problem using the greedy approach with efficient time and space complexity. Questions involving strings are prevalent in interviews. Such questions are generally easier to implement but require keen observation for designing proper solutions.

Hence learning never stops, and there is a lot more to learn.

Want to practice more greedy problems? Check out these blogs:

So head over to our practice platform CodeStudio to practice top problems on Data Structures and Algorithms, attempt Contests, mock tests, read interview experiences, and much more. Till then, Happy Coding!

Was this article helpful ?
0 upvotes