Problem Statement: Given a binary string and integer k, the task is to find the minimum number of flips required such that every substring of length k contains at least one set bit.
Examples:
Example 1: Input: str = “010” , k=1 Output: 2 Explanation: flip str[0] and then str[2] Example 2: Input: str = “110” , k=2 Output: 0
Solution
Disclaimer: Don’t jump directly to the solution, try it out yourself first.
Solution 1: Brute Force Approach
The brute force approach is to traverse the given string n-k times and for every index, traverse the nested loop for k times and check whether the given part of the string contains at least one.
If it is, this means no flips are required. Otherwise, the flip is required.
Let us understand using the given example
Let us understand using the given example For eg - given string as “01000001” , k=3 For 0th index of 01000001 010 -> It has at-least one present. So, no flipping required. For 1st index of 01000001 100-> It has at-least one present. So, no flipping required. For 2nd index of 01000001 000-> It do not have at-least one present. So one flipping required. Flipping will be done at last index of current substring, since this ‘1’ can be used for other strings also. Similarly in further steps, we will count the number of flips and return the count
Code:
C++ Code
#include<bits/stdc++.h>
using namespace std;
// Brute force approach
int findminflips(string str,int k)
{
int flips=0;
for(int i=0;i<str.length()-k;i++)
{
bool flag=false;
for(int j=0;j<k;j++)
{
if(str[j+i]=='1')
flag=true;
}
if(flag==false) // this means '1' is not present
{
str[i+k-1]='1';
flips++;
}
}
return flips;
}
int main()
{
string str="0100001";
int k=3;
cout<<"The minimum number of flips required is: "
<<findminflips(str,k)<<endl;
return 0;
}
Output:
The minimum number of flips required is: 1
Time Complexity: O(n*k)
Space complexity: O(1)
Java Code
import java.util.*;
public class Main {
// Brute force approach
public static int findminflips(char[] str, int n, int k) {
int flips = 0;
for (int i = 0; i < n - k; i++) {
boolean flag = false;
for (int j = 0; j < k; j++) {
if (str[i + j] == '1')
flag = true;
}
if (flag == false) // this means '1' is not present
{
str[i + k - 1] = '1';
flips++;
}
}
return flips;
}
public static void main(String args[]) {
String str = "0100001";
int n = 7;
int k = 3;
System.out.print("The minimum number of flips required is: ");
System.out.println(findminflips(str.toCharArray(), n, k));
}
}
Output:
The minimum number of flips required is: 1
Time Complexity: O(n*k)
Space complexity: O(1)
Solution 2: Optimized Way – Sliding Window Technique
Approach:
This technique is based on the sliding window in the current string.
Let us understand it
“01000001” , k=3 -> for the given window atleast one ‘1’ is present “01000001” , k=3 -> for the given window atleast one ‘1’ is present “01000001” , k=3 -> for the given window atleast one ‘1’ is not present. So flip the latest position 0 to 1 so that it can be usable by other next substrings Flips =1 String becomes = “01001001” “01001001” , k=3 -> for the given window atleast one ‘1’ is present “01001001” , k=3 -> for the given window atleast one ‘1’ is present “01001001” , k=3 -> for the given window atleast one ‘1’ is present So finally flips = 1 required in the given string
Code:
C++ Code
#include<bits/stdc++.h>
using namespace std;
// Sliding window technique
int findminflips(string str,int k)
{
int flips=0;
bool flag=false;
int prevposof1=-1;
for(int i=0;i<k;i++)
{
if(str[i]=='1')
{
prevposof1=i;
flag=true;
}
}
if(flag==false)
{
flips++;
prevposof1=k-1;
str[k-1]='1';
}
for(int i=k;i<str.length();i++)
{
if(str[i]=='1')
prevposof1=i;
// if currently i am standing at '0'
else if(prevposof1>i-k)
{
// no flip is required
}
else
{
flips++;
prevposof1=i;
}
}
return flips;
}
int main()
{
string str="0100001";
int k=3;
cout<<"The minimum number of flips required is: "
<<findminflips(str,k)<<endl;
return 0;
}
Output:
The minimum number of flips required is: 1
Time Complexity – O(N)
Space complexity – O(1)
Java Code
import java.util.*;
public class Main {
// Sliding window technique
public static int findminflips(char[] str, int n, int k) {
int flips = 0;
boolean flag = false;
int prevposof1 = -1;
for (int i = 0; i < k; i++) {
if (str[i] == '1') {
prevposof1 = i;
flag = true;
}
}
if (flag == false) {
flips++;
prevposof1 = k - 1;
}
for (int i = k; i < n; i++) {
if (str[i] == '1')
prevposof1 = i;
// if currently i am standing at '0'
else if (prevposof1 > i - k) {
// no flip is required
} else {
flips++;
prevposof1 = i;
}
}
return flips;
}
public static void main(String args[]) {
String str = "0100001";
int n = 7;
int k = 3;
System.out.print("The minimum number of flips required is: ");
System.out.println(findminflips(str.toCharArray(), n, k));
}
}
Output:
The minimum number of flips required is: 1
Time Complexity – O(N)
Space complexity – O(1)
Special thanks to Gurmeet Singh for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article