Do you think IIT Guwahati certified course can help you in your career?
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:
Flip S[0, 2] (string becomes ‘11110110’).
Flip S[4, 6] (string becomes ‘11111000’).
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.
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;
}
You can also try this code with Online C++ Compiler
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)
You can also try this code with Online Python Compiler
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();
}
}
}
You can also try this code with Online Java Compiler
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:
84+ registered