Given a binary string S and two positive integers A and B, the task is to check if the string consists of A independent pair of adjacent 0s and B independent number of 0s in the binary string or not. If found to be true, then print “Yes”. Otherwise, print “No”.
Examples:
Input: S = “10100”, A = 1, B = 1
Output: Yes
Explanation:
The given string consists of A (=1) pairs of adjacent 0s and B (=1) independent number of 0s.Input: S = “0101010”, A = 1, B = 2
Output: No
Explanation:
The given string has no pair of adjacent 0s.
Approach: Follow the steps below to solve the problem:
- Traverse the given string S using a variable, say i, and perform the following steps:
- If the current character is ‘0’ and its adjacent character is ‘0’ and A is at least 1, then decrease A by 1 and increase the pointer i by 1.
- Otherwise, if the current character is ‘0’ and B is at least 1, then decrease B by 1.
- After completing the above steps, if the value of A and B is 0, then print “Yes”. Otherwise, print “No”.
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 if there exists// A adjacent 0s and B 0s in the// given binary string or notvoid parking(string S, int a, int b){ // Traverse the string for (int i = 0; i < S.size(); i++) { if (S[i] == '0') { // If there are adjacent // 0s and a is positive if (i + 1 < S.size() && S[i + 1] == '0' && a > 0) { i++; a--; } // If b is positive else if (b > 0) { b--; } } } // Condition for Yes if (a == 0 && b == 0) { cout << "Yes\n"; } else cout << "No\n";}// Driver Codeint main(){ string S = "10100"; int A = 1, B = 1; parking(S, A, B);} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to check if there exists// A adjacent 0s and B 0s in the// given binary string or notstatic void parking(String S, int a, int b){ // Traverse the string for(int i = 0; i < S.length(); i++) { if (S.charAt(i) == '0') { // If there are adjacent // 0s and a is positive if (i + 1 < S.length() && S.charAt(i + 1) == '0' && a > 0) { i++; a--; } // If b is positive else if (b > 0) { b--; } } } // Condition for Yes if (a == 0 && b == 0) { System.out.print("Yes\n"); } else System.out.print("No\n");}// Driver Codepublic static void main (String[] args){ // Given string String S = "10100"; int A = 1, B = 1; parking(S, A, B);}}// This code is contributed by sanjoy_62 |
Python3
# Python3 program for the above approach# Function to check if there exists# A adjacent 0s and B 0s in the# given binary string or notdef parking(S, a, b): # Traverse the string for i in range(len(S)): if (S[i] == '0'): # If there are adjacent # 0s and a is positive if (i + 1 < len(S) and S[i + 1] == '0' and a > 0): i += 1 a -= 1 # If b is positive elif (b > 0): b -= 1 # Condition for Yes if (a == 0 and b == 0): print("Yes") else: print("No")# Driver Codeif __name__ == '__main__': S = "10100" A = 1 B = 1 parking(S, A, B) # This code is contributed by SURENDRA_GANGWAR |
C#
// C# program for the above approachusing System;class GFG{// Function to check if there exists// A adjacent 0s and B 0s in the// given binary string or notstatic void parking(string S, int a, int b){ // Traverse the string for(int i = 0; i < S.Length; i++) { if (S[i] == '0') { // If there are adjacent // 0s and a is positive if (i + 1 < S.Length && S[i + 1] == '0' && a > 0) { i++; a--; } // If b is positive else if (b > 0) { b--; } } } // Condition for Yes if (a == 0 && b == 0) { Console.WriteLine("Yes"); } else Console.WriteLine("No");}// Driver Codepublic static void Main (string[] args){ // Given string string S = "10100"; int A = 1, B = 1; parking(S, A, B);}}// This code is contributed by AnkThon |
Javascript
<script>// Function to check if there exists// A adjacent 0s and B 0s in the// given binary string or notfunction parking( S, a, b){ // Traverse the string for (var i = 0; i < S.length; i++) { if (S[i] == '0') { // If there are adjacent // 0s and a is positive if (i + 1 < S.length && S[i + 1] == '0' && a > 0) { i++; a--; } // If b is positive else if (b > 0) { b--; } } } // Condition for Yes if (a == 0 && b == 0) { document.write("Yes"+"<br>"); } else document.write( "No"+"<br>");}var S = "10100";var A = 1, B = 1;parking(S, A, B);//This code is contributed by SoumikMondal</script> |
Output
Yes
Time Complexity: O(N)
Auxiliary Space: O(1)
Approach:
We can count the number of pairs of adjacent 0s and the number of independent 0s in a single traversal of the string. While traversing the string, we maintain a count of the number of consecutive 0s encountered so far. Whenever we encounter a 1 or reach the end of the string, we update the counts of pairs and independent 0s based on the current count of consecutive 0s. Specifically, if the current count is 2 or more, we increment the count of pairs, and if the count is 1, we increment the count of independent 0s. Finally, we check if the counts match the required values.
- Initialize three variables count_pairs, count_independent, and count_consecutive to 0.
- Traverse the input string S from left to right.
- If the current character is ‘0’, increment the variable count_consecutive by 1.
- If the current character is ‘1’, update the counts of pairs and independent 0s based on the current count of consecutive 0s.
- If count_consecutive is greater than or equal to 2, increment count_pairs by 1.
- If count_consecutive is equal to 1, increment count_independent by 1.
- Reset count_consecutive to 0.
- After the traversal is complete, update the counts based on the final value of count_consecutive, since the traversal ends before updating the counts for the last group of consecutive 0s.
- If the final counts of pairs and independent 0s match the required values A and B, respectively, print “Yes”. Otherwise, print “No”.
C++
#include <iostream>#include <string>using namespace std;void check_string(string S, int A, int B) { int count_pairs = 0, count_independent = 0, count_consecutive = 0; for (int i = 0; i < S.length(); i++) { if (S[i] == '0') { count_consecutive++; } else { if (count_consecutive >= 2) { count_pairs++; } else if (count_consecutive == 1) { count_independent++; } count_consecutive = 0; } } if (count_consecutive >= 2) { count_pairs++; } else if (count_consecutive == 1) { count_independent++; } if (count_pairs == A && count_independent == B) { cout << "Yes\n"; } else { cout << "No\n"; }}int main() { string S = "10100"; int A = 1, B = 1; check_string(S, A, B); return 0;} |
Java
import java.util.*;public class Main { public static void main(String[] args) { String S = "10100"; int A = 1, B = 1; checkString(S, A, B); } public static void checkString(String S, int A, int B) { int countPairs = 0, countIndependent = 0, countConsecutive = 0; for (int i = 0; i < S.length(); i++) { if (S.charAt(i) == '0') { countConsecutive++; } else { if (countConsecutive >= 2) { countPairs++; } else if (countConsecutive == 1) { countIndependent++; } countConsecutive = 0; } } if (countConsecutive >= 2) { countPairs++; } else if (countConsecutive == 1) { countIndependent++; } if (countPairs == A && countIndependent == B) { System.out.println("Yes"); } else { System.out.println("No"); } }} |
Python3
def check_string(S, A, B): count_pairs = 0 count_independent = 0 count_consecutive = 0 for i in range(len(S)): if S[i] == '0': count_consecutive += 1 else: if count_consecutive >= 2: count_pairs += 1 elif count_consecutive == 1: count_independent += 1 count_consecutive = 0 if count_consecutive >= 2: count_pairs += 1 elif count_consecutive == 1: count_independent += 1 if count_pairs == A and count_independent == B: print("Yes") else: print("No")if __name__ == "__main__": S = "10100" A = 1 B = 1 check_string(S, A, B) |
C#
using System;public class GFG{ public static void CheckString(string S, int A, int B) { int countPairs = 0, countIndependent = 0, countConsecutive = 0; for (int i = 0; i < S.Length; i++) { if (S[i] == '0') { countConsecutive++; } else { if (countConsecutive >= 2) { countPairs++; } else if (countConsecutive == 1) { countIndependent++; } countConsecutive = 0; } } // Check for consecutive '0's at the end of the string if (countConsecutive >= 2) { countPairs++; } else if (countConsecutive == 1) { countIndependent++; } // Check if the counts of pairs and independent '0's match the given values A and B if (countPairs == A && countIndependent == B) { Console.WriteLine("Yes"); } else { Console.WriteLine("No"); } } public static void Main() { string S = "10100"; int A = 1, B = 1; CheckString(S, A, B); // To pause the console before exiting Console.ReadLine(); }} |
Javascript
// JavaScript code for above appoachfunction checkString(S, A, B) { let countPairs = 0, countIndependent = 0, countConsecutive = 0; for (let i = 0; i < S.length; i++) { if (S[i] === '0') { countConsecutive++; } else { if (countConsecutive >= 2) { countPairs++; } else if (countConsecutive === 1) { countIndependent++; } countConsecutive = 0; } } // checking the pairs if (countConsecutive >= 2) { countPairs++; } else if (countConsecutive === 1) { countIndependent++; } // checking the conditions given if (countPairs === A && countIndependent === B) { console.log("Yes"); } else { console.log("No"); }}// Driver Codeconst S = "10100";const A = 1, B = 1;checkString(S, A, B); |
Output
Yes
Time Complexity: O(n), where n is the length of the input string.
Space Complexity: O(1), since we only use a constant amount of extra memory to store the counts.
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
