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

0 0 6 minutes read

Given a binary string S of size N and a number K, the task is to find if all the ‘0’s can be changed into ‘1′s in any number of operations. In one operation, if S[i] is initially ‘1’, then all ‘0‘s in the range [i+1, i+K] can be changed to ‘1’s, for 0≤i<N-K.

Examples:

Input: S=”100100″, N=6, K=2
Output: YES
Explanation: S[0] can be used to change S[1] and S[2] into 1s
S[3] can be used to change S[4] and S[5] into 1s

Input: S=”110000″, N=6, K=2
Output: NO

Naive Approach: The simplest approach is to traverse the string in a reverse manner and if ‘0’ is encountered, check if the position of the nearest ‘1’ on the left is more than K indices away. If true, then print “NO”.

Time Complexity: O(N*K)
Auxiliary Space: O(1)

Efficient Approach: To optimize the above approach, the idea is to use a stack. Follow the steps below to solve the problem:

Initialize two variables flag and count as 1 and 0 respectively to store the result and to count the number of ‘0′s that have been changed by the last occurrence of ‘1′.
Initialize an empty stack st.
Traverse the string S, and do the following:
- If stack is empty:
  - If the current element is ‘0’, change flag to 0 and break, as this ‘0′ cannot be changed to ‘1’.
  - Otherwise, update count to 0 and push 1 to st.
- Otherwise:
  - If the current element is ‘0’, do the following:
    - Increment count by 1.
    - If count becomes equal to K, pop the stack st and update count to 0
  - Else, update count to 0.
If the value of flag is 1, print “YES”, otherwise print “NO” as the result.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to check whether all 0s
// in the string can be changed into 1s
void changeCharacters(string S, int N, int K)
{
    int flag = 1;
 
    // Store the count of 0s converted
    // for the last occurrence of 1
    int count = 0;
 
    // Declere a stack
    stack<char> st;
 
    // Traverse the string, S
    for (int i = 0; i < N; i++) {
 
        // If stack is empty
        if (st.empty()) {
 
            // There is no 1 that can
            // change this 0 to 1
            if (S[i] == '0') {
                flag = 0;
                break;
            }
 
            // Push 1 into the stack
            count = 0;
            st.push(S[i]);
        }
        else {
            if (S[i] == '0') {
                count++;
 
                // The last 1 has reached
                // its limit
                if (count == K) {
                    st.pop();
                    count = 0;
                }
            }
 
            // New 1 has been found which
            // can now change at most K 0s
            else {
                count = 0;
            }
        }
    }
 
    // If flag is 1, print "YES"
    // else print "NO"
    if (flag)
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
}
 
// Driver code
int main()
{
    // Given Input
    string S = "100100";
    int N = S.length();
    int K = 2;
 
    // Function call
    changeCharacters(S, N, K);
 
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
 
class GFG{
 
// Function to check whether all 0s
// in the string can be changed into 1s
static void changeCharacters(String S, int N, int K)
{
    int flag = 1;
 
    // Store the count of 0s converted
    // for the last occurrence of 1
    int count = 0;
 
    // Declere a stack
    Stack<Character> st = new Stack<>();  
 
    // Traverse the string, S
    for(int i = 0; i < N; i++)
    {
         
        // If stack is empty
        if (st.empty()) 
        {
             
            // There is no 1 that can
            // change this 0 to 1
            if (S.charAt(i) == '0')
            {
                flag = 0;
                break;
            }
 
            // Push 1 into the stack
            count = 0;
            st.push(S.charAt(i));
        }
        else
        {
            if (S.charAt(i) == '0') 
            {
                count++;
                 
                // The last 1 has reached
                // its limit
                if (count == K) 
                {
                    st.pop();
                    count = 0;
                }
            }
 
            // New 1 has been found which
            // can now change at most K 0s
            else
            {
                count = 0;
            }
        }
    }
 
    // If flag is 1, print "YES"
    // else print "NO"
    if (flag == 1)
        System.out.print("YES");
    else
        System.out.print("NO");
}
 
// Driver code
public static void main(String args[])
{
     
    // Given Input
    String S = "100100";
    int N = S.length();
    int K = 2;
 
    // Function call
    changeCharacters(S, N, K);
}
}
 
// This code is contributed by ipg2016107

Python3

# Python3 program for the above approach
 
# Function to check whether all 0s
# in the string can be changed into 1s
def changeCharacters(S, N, K):
    flag = 1
 
    # Store the count of 0s converted
    # for the last occurrence of 1
    count = 0
 
    # Declere a stack
    st = []
 
    # Traverse the string, S
    for i in range(N):
 
        # If stack is empty
        if len(st) == 0:
 
            # There is no 1 that can
            # change this 0 to 1
            if (S[i] == '0'):
                flag = 0
                break
 
            # Push 1 into the stack
            count = 0
            st.append(S[i])
        else:
            if (S[i] == '0'):
                count+=1
 
                # The last 1 has reached
                # its limit
                if (count == K):
                    del st[-1]
                    count = 0
 
            # New 1 has been found which
            # can now change at most K 0s
            else:
                count = 0
 
    # If flag is 1, pr"YES"
    # else pr"NO"
    if (flag):
        print("YES")
    else:
        print("NO")
 
# Driver code
if __name__ == '__main__':
    # Given Input
    S = "100100"
    N = len(S)
    K = 2
 
    # Function call
    changeCharacters(S, N, K)
 
# This code is contributed by mohit kumar 29.

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
  
// Function to check whether all 0s
// in the string can be changed into 1s
static void changeCharacters(string S, int N, int K)
{
    int flag = 1;
 
    // Store the count of 0s converted
    // for the last occurrence of 1
    int count = 0;
 
    // Declere a stack
    Stack<char> st = new Stack<char>();
 
    // Traverse the string, S
    for(int i = 0; i < N; i++) {
 
        // If stack is empty
        if (st.Count==0) {
 
            // There is no 1 that can
            // change this 0 to 1
            if (S[i] == '0') {
                flag = 0;
                break;
            }
 
            // Push 1 into the stack
            count = 0;
            st.Push(S[i]);
        }
        else {
            if (S[i] == '0') {
                count++;
 
                // The last 1 has reached
                // its limit
                if (count == K) {
                    st.Pop();
                    count = 0;
                }
            }
 
            // New 1 has been found which
            // can now change at most K 0s
            else {
                count = 0;
            }
        }
    }
 
    // If flag is 1, print "YES"
    // else print "NO"
    if (flag == 1)
       Console.Write("YES");
    else
       Console.Write("NO");
}
 
// Driver code
public static void Main()
{
    // Given Input
    string S = "100100";
    int N = S.Length;
    int K = 2;
 
    // Function call
    changeCharacters(S, N, K);
 
}
}
 
// This code is contributed by SURENDRA_GANGWAR.

Javascript

<script>
 
// JavaScript program for the above approach
 
 
// Function to check whether all 0s
// in the string can be changed into 1s
function changeCharacters(S, N, K) {
    let flag = 1;
 
    // Store the count of 0s converted
    // for the last occurrence of 1
    let count = 0;
 
    // Declere a stack
    let st = new Array();
 
    // Traverse the string, S
    for (let i = 0; i < N; i++) {
 
        // If stack is empty
        if (st.length == 0) {
 
            // There is no 1 that can
            // change this 0 to 1
            if (S[i] == '0') {
                flag = 0;
                break;
            }
 
            // Push 1 into the stack
            count = 0;
            st.push(S[i]);
        }
        else {
            if (S[i] == '0') {
                count++;
 
                // The last 1 has reached
                // its limit
                if (count == K) {
                    st.pop();
                    count = 0;
                }
            }
 
            // New 1 has been found which
            // can now change at most K 0s
            else {
                count = 0;
            }
        }
    }
 
    // If flag is 1, print "YES"
    // else print "NO"
    if (flag == 1)
        document.write("YES");
    else
        document.write("NO");
}
 
// Driver code
 
// Given Input
let S = "100100";
let N = S.Length;
let K = 2;
 
// Function call
changeCharacters(S, N, K);
 
 
// This code is contributed by _saurabh_jaiswal
 
</script>

Output

YES

Time Complexity: O(N)
Auxiliary Space: O(1) since at most one character is present in the stack at any moment

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!