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:

Flip S[0, 2] (string becomes ‘11110110’).

Flip S[4, 6] (string becomes ‘11111000’).

Flip S[5, 7] (string becomes ‘11111111’).

Get the tech career you deserve, faster!

Connect with our expert counsellors to understand how to hack your way to success

User rating 4.7/5

1:1 doubt support

95% placement record

Akash Pal

Senior Software Engineer

326% Hike After Job Bootcamp

Himanshu Gusain

Programmer Analyst

32 LPA After Job Bootcamp

After Job Bootcamp

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.

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.

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: