Convert given Binary string S to all 1s by changing all 0s to 1s in range [i+1, i+K] if S[i] is ‘1’

Aman Chourasiya
Last Updated: May 23, 2022
Difficulty Level :
EASY

Introduction

In this blog, we are going to discuss a problem based on binary strings. Binary strings based coding problems are widely asked in programming contests and coding interviews. In this problem, we will use the stack data structure to solve the problem. We will also learn a greedy solution to the problem. The stack data structure proves to be very helpful while solving binary strings related problems.

Problem Statement

Ninja has given you a binary string consisting of '0's and '1's and an integer K. You need to check if it is possible to convert the string to all '1's. In other words, if it is possible to convert all '0's to '1's in the string. You are allowed to perform the following operation any number of times - 

If S[i] is '1', then you can change all '0's in the range [i+1, i+K] to '1's provided i+K < N where N is the length of the string.

Note that you cannot use newly created '1's to perform the operation mentioned above.

Example 1:

Input

S = 100101

K = 2

Output

True

Explanation

Example 2:

You can use the first and third characters and perform the above operation to convert the string to all '1's.

Input

S = 111000

K = 2

Output

False

Explanation

You cannot change the last '0' to '1' whichever '1' to use. Note that you cannot use the new '1's to do the operation.

Approach 1

This problem can be solved using a greedy approach. The idea is to traverse the string in reverse order, and for each '0' encountered, check if the nearest '1' (in left direction) is more than K indices away. If it is true or there is no '1' on the left, the answer would be false. Otherwise, true.

The logic behind this approach is simple: If, for any '0', the nearest '1' on the left is more than K indices away, that ' 0' cannot be turned to '1'.

Algorithm

  1. Initialize the answer as true.
  2. Traverse the string from the back and let the current index be i.
  3. If S[i] == '0', traverse from the current index i to the leftmost index k distance away.
  4. If no '1' is found, the answer will be false.

Implementation in C++

#include<bits/stdc++.h>
using namespace std;

int main(){
    string s; cin>>s; // taking input.
    int k; cin>>k;

    int n = s.length();
    bool ans = true;

    for(int i = n - 1; i >= 0; i--){
        if(s[i] == '0'){

            int found = 0;
            for(int j = i; j >= max(0, i - k); j--){ // more to the left by at most k distance.
                if(s[i] == '1') {
                    found = 1; break; // found a '1' on the left less than k distance away.
                }
            }
            if(found == 0){ // if not found, the current '0' cannot be converted to '1'.
                ans = false; break;
            }
            
        }
        if(ans == false) break;
    }

    if(ans) cout<<"true"<<endl;
    else cout<<"false"<<endl;
}

 

Implementation in Python

def main():
    s=(input())
    k = int(input ())
    n=len(s)
    ans=True
    
    for i in range(n-1,-1,-1):
        if(s[i]=='0'):
            found=int(0);
            for i in range(i,max(0, i - k),-1):
                if(s[i]=='1'):
                    found=int(1)
                    break
            #if not found, the current '0' cannot be converted to '1'.    
            if(found==0):
                ans=False
                break
        if(ans==False):
            break
    
    if(ans==True):
        print("True")
    else:
        print("False")
        
if __name__=="__main__":
    main()

 

Implementation in Java

import java.util.*;


class BinaryStringConversion {
    public static void main(String[] args) {
        Scanner sc= new Scanner(System.in);
         
        String s=sc.nextLine();
        
        int n=s.length();
        
        int k=sc.nextInt();
        
        boolean ans=true;
        
        for(int i=n-1;i>=0;i--)
        {
            if(s.charAt(i)=='0')
            {
                int found=0;
                for(int j=i;j>=Math.max(0,i-k);j--)
                {
                    if(s.charAt(j) == '1')
                    {
                        found=1;
                        break;
                    }
                }
                if(found==0)
                {
                    ans=false;
                    break;
                }
                
            }
            if(ans==false)
            {
                break;
            }
        }
        
         if(ans) System.out.println("True");
         else System.out.println("False");
        
        
    }
}

Input

S = 111000

K = 2

Output

false

Complexity Analysis

Time Complexity:

The time complexity of the above approach is O(N * K) as for each '0', we need to check the value of K immediate left characters.

Space Complexity:

The space complexity of the above approach is O(1), as we are using constant space to run the algorithm.

Approach 2

We can optimize the time complexity of the above approach by pre-computing an array arr that will store the position of immediate '1' on the left for each index in the string. Now, for each index i, we need not traverse the left characters. We can check the value stored at arr[i] if it satisfies the condition or not.

Algorithm

  1. Initialize the answer as true.
  2. Pre-compute the array arr as outlined in the approach above.
  3. To compute the array arr, create a variable nearestOne and initialize it with -1.
  4. Traverse the string and let the current index be i. If s[i] == '1', update arr[i] = i and nearestOne to i.
  5. Otherwise, arr[i] = nearestOne.
  6. Traverse the string and let the current index be i.
  7. If S[i] == '0', then check for arr[i].
  8. If arr[i] equals -1 or i - arr[i] > k, answer would be false. If arr[i] equals -1, it implies that there is no '1' on the left of ith index.

Implementation in C++

#include<bits/stdc++.h>
using namespace std;

int main(){
    string s; cin>>s; // taking input.
    int k; cin>>k;

    int n = s.length();
    bool ans = true;

    vector<int> arr(n,-1); // precomputed array.
    int nearestOne = -1;

    for(int i = 0; i < n; i++){
        if(s[i] == '1'){
            arr[i] = i; 
            nearestOne = i; // updated the nearest one to be i.
        }
        else arr[i] = nearestOne; // otherwise, update with nearestOne.
    }

    for(int i = n - 1; i >= 0; i--){
        if(s[i] == '0'){

            if(arr[i] == -1 || i - arr[i] > k){ // if arr[i] == -1, then no '1' on the left. If i - arr[i] > k, the nearest '1' is more than k indices away.
                ans = false;
            }

        }
        if(ans == false) break;
    }

    if(ans) cout<<"true"<<endl;
    else cout<<"false"<<endl;
}

Implementation in Python

def main():
    s=(input())
    k = int(input ())
    n=len(s)
    ans=True
    
    arr=[]
    
    nearestOne=int(-1)
   
    for i in range(0,n,1):
        arr.append(int(-1))
    
    for i in range(0,n,1):
        if(s[i]=='1'):
            arr[i]=int(i)
            nearestOne= int(i)
        else:
            arr[i]=nearestOne
            
    for i in range(n-1,-1,-1):
        if(s[i]=='0'):
            if(arr[i]==-1 or i-arr[i]>k):
                ans=False
        if(ans==False):
            break;
    
    if(ans==True):
        print("True")
    else:
        print("False")
        
if __name__=="__main__":
    main()

        

Implementation in Java

import java.util.*;


class BinaryStringConversion {
    public static void main(String[] args) {
        Scanner sc= new Scanner(System.in);
         
        String s=sc.nextLine();
        
        int n=s.length();
        
        int k=sc.nextInt();
        
        int nearestOne=-1;
        
        boolean ans=true;
        
        Vector<Integer> arr= new Vector<Integer>();
        
        for(int i=0;i<n;i++)
        {
            arr.add(-1);
        }
        
        for(int i = 0; i < n; i++){
        if(s.charAt(i) == '1'){
            arr.set(i,i) ;
            nearestOne = i; // updated the nearest one to be i.
        }
        else arr.set(i, nearestOne); // otherwise, update with nearestOne.
    }


    for(int i = n - 1; i >= 0; i--){
        if(s.charAt(i) == '0'){


            if(arr.get(i) == -1 || i - arr.get(i) > k){ // if arr[i] ==-1, then no '1' on the left. If i - arr[i] > k, the nearest '1' is more than k indices away.
                ans = false;
            }


        }
        if(ans == false) break;
    }


        
         if(ans) System.out.println("True");
         else System.out.println("False");
        
        
    }
}

Input

S = 111000

K = 2
Output

false

Complexity Analysis

Time Complexity:

The time complexity of the above approach is O(N), as for each index, we use the pre-computed value in O(1) time.

Space Complexity:

The space complexity of the above approach is O(N), as we use array arr of size N for pre-computation of nearest '1'.

Approach 3

In this approach, we will solve the problem using the stack data structure. The idea is to maintain a stack while we traverse the string. We need to check for a few corner cases as we move forward. 

Maintain a count of how many '0's have been encountered so far.

If we encounter a '1' and the stack is empty, push '1' to the stack. Otherwise, if the current character is '1' and the stack is non-empty, move forward and update the count variable to 0. It is because, for the current '1' character, there is no zero yet converted by it.

If the current character is '0' and the stack is empty, the answer would be false. As for the current '0' character, there is no '1' on the left to convert it to '1'.

Otherwise, increase the count by 1. If the count variable equals K, pop the stack and update the count variable to 0.

Algorithm

  1. Initialize two variables ans and count as true and 0 respectively to store the result and count the number of ‘0s that the last occurrence of '1' has changed.
  2. Initialize an empty stack st.
  3. Traverse the string S, and do the following:
  4. If the stack is empty:
    1. If the current element is 0, change the ans variable to false and break, as this ‘0 cannot be changed to 1.
    2. Otherwise, update count to 0 and push 1 to st.
  5. Otherwise:
    1. If the current element is '0', do the following:
      1. Increment count by 1.
      2. If count becomes equal to K, pop the stack st and update the count variable to 0.
    2. Else, update count to 0.

Implementation in C++

#include<bits/stdc++.h>
using namespace std;

int main(){
    string s; cin>>s; // taking input.
    int k; cin>>k;

    int n = s.length();
    bool ans = true;

    stack<int> st; // stack data structure initialization.

    int count = 0; // to count the number of zeros.

    for(int i = 0; i < n; i++){
        if(s[i] == '1'){
            if(st.empty()) st.push(1); // push if empty and update count.
            count = 0;
        }
        else{
            if(st.empty()){ 
                ans = false; break; // if empty then either no '1' on the left or the nearest one is more than k indices away.
            }
            count++; // increment the count as '0' is encountered.
            if(count == k){ // if count equals k, then the nearest '1' should be popped.
                st.pop();
                count = 0; // and update count to 0 as all the zeroes in between are handled.
            }
        }
    }

    if(ans) cout<<"true"<<endl;
    else cout<<"false"<<endl;
}

Implementation in Python

def main():
    s=(input())
    k = int(input ())
    n=len(s)
    ans=True
    count=0
    st=[]
    
    for i in range(n):
        if(s[i]=='1'):
            if(len(st)==0):
                st.append(1)
                count=0
        else:
            if(len(st)==0):
                ans=False
                break
            count+=1
            if(count==k):
                del st[-1]
                count=0
    
    if(ans==True):
        print("True")
    else:
        print("False")
        
if __name__=="__main__":
    main()
        


Implementation in Java

import java.util.*;


class BinaryStringConversion {
    public static void main(String[] args) {
        Scanner sc= new Scanner(System.in);
         
        String s=sc.nextLine();
        
        int n=s.length();
        
        int k=sc.nextInt();
        
        boolean ans=true;
        int count=0;
        
        Stack<Character> st = new Stack<>();
        
        for(int i = 0; i < n; i++){
            if(s.charAt(i)=='1')
            {
                if(st.empty())
                {
                    st.push(s.charAt(i));
                    count=0;
                }
            }
            else
            {
                if(st.empty())
                {
                    ans=false;
                    break;
                }
                count+=1;
                if(count==k)
                {
                    st.pop();
                    count=0;
                }
            }
        }


        
         if(ans) System.out.println("True");
         else System.out.println("False");
        
        
    }
}


Input

S = 111000

K = 2
Output

false

Complexity Analysis

Time Complexity:

The time complexity of the above approach is O(N), as the pop and push operation of the stack data structure is O(1), and they are called at most N times.
Space Complexity:

The space complexity of the above approach is O(1), as, at any instant, the size of the stack can be at most one.

Conclusion

In this blog, we learned three approaches to solve the problem. The first two approaches summarised a greedy algorithm to solve the problem. Greedy algorithms are always the first to go algorithms to think. We also discussed how to optimize the first greedy approach to reduce the time complexity. Then we discussed the most optimal approach using the stack data structure. The stack data structures are widely used to solve problems based on binary strings. Various problems based on binary strings can be solved by using stack and queue data structures.

 

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

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

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think