Do you think IIT Guwahati certified course can help you in your career?
No
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 stackdata structure to solve the problem. We will also learn a greedy solution to the problem. The stack data structure is very helpful while solving binary string-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
You can use the first and third characters and perform the above operation to convert the string to all '1's.
Example 2:
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 Bruteforce
Approach
We need to iterate through each character in the string and check if a '1' exists to its left such that the distance between the two indices is at most 'k'. This is done by searching at most 'k' characters to the left of each '0' in the string.
If we can't find such a '1' for a particular '0', we set a boolean variable 'result' to false and break out of the loop. If we iterate through the entire string without encountering such a case, we set ‘result’ to true.
Finally, we print the value of ‘result’ to indicate whether the given condition is satisfied by the input string and integer 'k'.
Algorithm
For each character in the string, check if it is a '0'. For the below example
(K=2)
If the character is a '0', search the previous k characters in the string to see if there is a '1' among them.
If there is a '1' among the previous k characters, move on to the next character in the string.
If there is no '1' among the previous k characters, record that the condition is not satisfied and stop searching.
Once all '0's in the string have been checked, output whether the condition is satisfied for all of them.
(In the above case the K is not increasing greater than 2, so the Result is true.)
Implementation
#include <bits/stdc++.h>
using namespace std;
// This function checks if there is at least one '1' within a distance of k positions
// to the left of each '0' in the input string
bool CheckOnesAroundZeros(const string& inputString, const int& k) {
bool isSatisfied = true;
int stringLength = inputString.length();
// Iterate through the string
int i = 0;
do {
// Check if the current character is '0'
switch (inputString[i]) {
case '0': {
bool isFound = false;
// Search for '1' within a distance of k positions to the left of the current '0'
int j = i - 1;
while (j >= max(0, i - k)) {
if (inputString[j] == '1') {
isFound = true;
break;
}
j--;
}
// If no '1' is found within the specified distance, set isSatisfied to false
if (!isFound) {
isSatisfied = false;
break;
}
}
}
i++;
} while (isSatisfied && i < stringLength);
// Return whether the condition is satisfied for all '0's in the string
return isSatisfied;
}
int main() {
// Get input string and k
string inputStr="1010010100";
int inputK=2;
// Check if satisfied for all '0's in the string
bool result = CheckOnesAroundZeros(inputStr, inputK);
if (result)
cout << "true" << endl;
else
cout << "false" << endl;
return 0;
}
Output
Complexity
Time Complexity
The time complexity of the above code is O(n * k) because it goes through each character in the input string and, for each "0" character it encounters, it looks up to k characters to the left to see if there is a "1". This process is repeated for each "0" character in the input string, which is why the time complexity grows proportionally with n and k.
Space Complexity
The space complexity of the code is O(1), which means that the amount of memory used by the code does not depend on the size of the input string or the value of k. This is because the code only uses constant memory, regardless of the input string size.
Approach 2 Precomputation
We can optimise 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 whether the value stored at arr[i] satisfies the condition, where arr[i] is the precomputation array.
Algorithm
Initialise the answer as true.
Pre-compute the array arr as outlined in the approach above.
To compute the array arr, create a variable nearestOne and initialise it with -1.
Traverse the string and let the current index be i.
If s[i] == '1', update arr[i] = i and nearestOne to i.
Otherwise, arr[i] = nearestOne.
Traverse the string and let the current index be i.
If S[i] == '0', then check for arr[i].If arr[i] equals -1 or i - arr[i] > k, the answer would be false. If arr[i] equals -1, it implies that there is no '1' on the left of the ith index.
Dry Run
Initialize string s to "101100100" and integer k to 2.
Initialise n to the length of s, which is 9.
Initialise boolean variable ans to true.
Create a vector arr of length n initialised to -1.
Initialise nearestOne to -1.
Loop through each character c in the string s.
If c is '1', set arr[i] to i and update nearestOne to i.
If c is '0', set arr[i] to nearestOne.
Loop through each character c in the string s, starting from the end.
If c is '0', check if arr[i] is -1 or if i - arr[i] is greater than k.
If either condition is true, set ans to false and break out of the loop.
If ans is still true, print "true". Otherwise, print "false".
In this case, the program will output "true" since we can convert the string to all 1s by changing the 0 at index 5 to 1 and the 0 at index 7 to 1.
Implementation in C++
#include<bits/stdc++.h>
using namespace std;
bool solution(string s,int k){
int n = s.length();
bool ans = true;
// precomputed array.
vector<int> arr(n,-1);
int nearestOne = -1;
for(int i = 0; i < n; i++){
if(s[i] == '1'){
arr[i] = i;
// updated the nearest one to be i.
nearestOne = i;
}
// otherwise, update with nearestOne.
else arr[i] = nearestOne;
}
for(int i = n - 1; i >= 0; i--){
if(s[i] == '0'){
/*
if arr[i] == -1, then no '1' on the left.
If i - arr[i] > k, the nearest '1' is more than k indices away.
*/
if(arr[i] == -1 || i - arr[i] > k){
ans = false;
}
}
if(ans == false) break;
}
//returning ans
return ans;
}
int main(){
// Given String
string s="101100100";
int k=2;
//calculating solution
bool ans=solution(s,k);
if(ans) cout<<"True"<<endl;
else cout<<"False"<<endl;
}
Output
Implementation in Java
import java.util.*;
public class Main {
public static boolean solution(String s,int k ){
int n=s.length();
//Initializing variable
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) ;
// updated the nearest one to be i.
nearestOne = i;
}
// otherwise, update with nearestOne.
else arr.set(i, nearestOne);
}
for(int i = n - 1; i >= 0; i--){
if(s.charAt(i) == '0'){
/*
if arr[i] ==-1, then no '1' on the left.
If i - arr[i] > k, the nearest '1' is more than k indices away.
*/
if(arr.get(i) == -1 || i - arr.get(i) > k){
ans = false;
}
}
if(ans == false) break;
}
//returning ans
return ans;
}
public static void main(String[] args) {
//String
String s="101100100";
int k=2;
//Calculating Solution
boolean ans=solution(s,k);
if(ans) System.out.println("True");
else System.out.println("False");
}
}
Output
Complexity Analysis
Time Complexity:
The time complexity of the above approach is O(N) because, for each index, we use the already calculated 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 Stack
Here 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.
First, count 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.
The answer would be false if the current character is '0' and the stack is empty. As for the current '0' character, no '1' is 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
First, we need to initialise two variables ans and countas trueand 0, respectively, to store the result and count the number of ‘0′s that the last occurrence of '1' has changed.
Again we need to initialise an empty stack ( st refers to stackcheck ).
Traverse the string S, and do the following:
If the stack is empty:
If the current element is ‘0’, change the ans variableto falseand break, as this ‘0′ cannot be changed to ‘1’.
Otherwise, update the count to 0 and push 1 to stackcheck .
Else we have to follow the following:
If the current element is '0',Increment count by 1.
If the count becomes equal to K, pop the stack stackcheck and update the count variable to 0.
Else, update the count to 0.
Dry Run
Let’s see if the input string is s="101100100" and k=2.
n=9 (length of s )
ans=true
( st refers to stackcheck ) is an empty stack
count=0
Since k<n, continue to the next step.
Loop through each character in s: ( st refers to stackcheck )
Check if the last index encountered is a 0 and the nearest 1 is within k indices.
Since ans=true and stackcheck is empty, output "true".
Implementation in C++
#include<bits/stdc++.h>
using namespace std;
bool checkForIfStringValid(string s, int k) {
int n = s.length();
bool ans = true;
stack<int> stackcheck;
int count = 0;
// Check if k is greater than or equal to n
if (k >= n) {
return true;
}
int i = 0;
while (i < n) {
switch (s[i]) {
case '1':
// push if empty and update count.
if (stackcheck.empty()) {
stackcheck.push(i);
}
count = 0;
i++;
break;
case '0':
if (stackcheck.empty()) {
ans = false;
// exit the loop
i = n;
} else {
count++;
if (count == k) {
stackcheck.pop();
count = 0;
}
i++;
}
break;
}
}
/*
Check if last index encountered is a 0 and the nearest 1 is within k indices
*/
if (!stackcheck.empty() && (n - 1 - stackcheck.top() <= k)) {
stackcheck.pop();
}
if(ans && stackcheck.empty()) {
return true;
}
else {
return false;
}
}
int main(){
string s="1001100100";
int k=2;
bool isValid = checkForIfStringValid(s, k);
if(isValid) {
cout<<"true"<<endl;
} else {
cout<<"false"<<endl;
}
}
Output
Implementation in Java
import java.util.Stack;
public class Main {
public static boolean checkForIfStringValid(String s, int k) {
int n = s.length();
boolean ans = true;
Stack<Integer> stackcheck = new Stack<>();
int count = 0;
// Check if k is greater than or equal to n
if (k >= n) {
return true;
}
int i = 0;
while (i < n) {
switch (s.charAt(i)) {
case '1':
// push if empty and update count.
if (stackcheck.empty()) {
stackcheck.push(i);
}
count = 0;
i++;
break;
case '0':
if (stackcheck.empty()) {
ans = false;
// exit the loop
i = n;
} else {
count++;
if (count == k) {
stackcheck.pop();
count = 0;
}
i++;
}
break;
}
}
/*
Check if last index encountered is a 0 and the nearest 1 is within k indices
*/
if (!stackcheck.empty() && (n - 1 - stackcheck.peek() <= k)) {
stackcheck.pop();
}
if (ans && stackcheck.empty()) {
return true;
}
else {
return false;
}
}
public static void main(String[] args) {
String s = "1001100100";
int k = 2;
boolean isValid = checkForIfStringValid(s, k);
if (isValid) {
System.out.println("true");
}
else {
System.out.println("false");
}
}
}
Output
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.
Frequently Asked Questions
What is the Time Complexity of the push and pop operations?
The push and pop operations on a stack, along with the top operation, are carried out in a constant time, i.e., O(1).
What is the best case of Time Complexity that is obtained for a solution to this problem?
The Best Time Complexity for this problem is O(N), obtained when a solution involving a stack is used, i.e., Approach 3 above.
What is the difference between a stack data structure and a queue data structure?
The stack data structure is a LIFO type i.e. Last In First Out type data structure, whereas the Queue data structure is a FIFO type i.e. First In First Out type data structure which means the most recent element inserted in a stack will be popped first whereas in a queue the elements are popped in the order they are inserted.
Can a stack data structure be implemented using any other data structures?
Yes, stacks can be implemented using various data structures such as arrays, Linked Lists, Queues, etc.
Can a stack be implemented using an array or a linked list?
Yes, a stack can be implemented using either an array or a linked list. In fact, these are the two most common ways of implementing a stack.
Conclusion
In this blog, we learned three approaches to solving the problem. The first two approaches summarised a greedy algorithm to solve the problem. Greedy algorithmsare 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 platformCoding Ninjas Studioto practice top problems, attempt mock tests, readinterview experiences, and much more. Till then, Happy Coding!