Given a binary string consisting of 0s and 1s and ‘?’ characters and an integer K, it is allowed to replace ‘?’ with 0 or 1, the task is to check if there is a unique way of replacing ‘?’ with 0s and 1s such that there is only 1 substring of K length containing all 1s. If there is only one way to do so print “Yes” otherwise “No” in all other cases.
Note: There should be only 1 possible position of K length substring of all 1s for the answer to be Yes.
Examples:
Input: S = ?1?0, K = 2
Output: No
Explanation: There are two possible ways which satisfies all the conditons, S = 1100, 0110. Hence due to multiple ways the output would be No.Input: S = 00?1???10?, K = 5
Output: Yes
Explanation: There is only one possible string S = 0001111100 that have exactly K length substring of all 1s and is the only possible way.
Naive Approach: The basic way to solve the problem is as follows:
For every K-length substring, we can make that all 1s only if all characters in the substring are ‘1’s or ‘?’s and all other characters outside that substring are all ‘0’s or ‘?’s.
We can check this with brute force for every K-length substring and count the respective number of characters.
Time complexity: O(|s|K)
Auxiliary Space: O(1)
Efficient-Approach: To solve the problem follow the below idea:
Moving from Si to Si+K we can keep track of the changes. Now keep count of the number of valid ways. If there is only 1 way, then print “Yes” or else “No”.
Steps that were to follow the above approach:
- Make two prefix arrays sum and tot where sum[i] stores the number of 0s up to index i and tot[i] stores the number of 1s up to index i respectively in string S.
- Now iterate in the range [k, n] where n is the length of string s.
- To check if we can make a valid substring, we have to check three conditions: (tot[i – k] == 0 and tot[n] – tot[i] == 0 and sum[i] – sum[i – k] == 0)
- Initialize a variable cnt = 0, to store the number of valid substrings.
- Whenever we find these three conditions true for a substring increment cnt = cnt + 1.
- Check if cnt == 1 at the end. If cnt == 1, then print “Yes” or else “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 the given// string is validstring isValidString(string s, int k){ // Getting size of the string int n = s.size(); // Initializing prefix arrays vector<int> sum(n + 1, 0); vector<int> tot(n + 1, 0); // Precomputing prefix arrays for (int i = 0; i < n; i++) { sum[i + 1] += sum[i]; if (s[i] == '0') sum[i + 1]++; if (s[i] == '1') tot[i + 1]++; tot[i + 1] += tot[i]; } // Initializing cnt to count total // number of valid substrings. int cnt = 0; for (int i = k; i <= n; i++) { // Condition for a valid substring if (tot[i - k] == 0 and tot[n] - tot[i] == 0 and sum[i] - sum[i - k] == 0) // Incrementing cnt to keep // track of valid substrings. cnt++; } // Returning the answer if (cnt == 1) return "Yes"; return "No\n";}// Driver's codeint main(){ string s = "00?1???10?"; int k = 5; // Function Call cout << isValidString(s, k); return 0;} |
Java
// Java program for the above approachimport java.util.*;public class Main { // Function to check if the given // string is valid static String isValidString(String s, int k) { // Getting size of the string int n = s.length(); // Initializing prefix arrays int[] sum = new int[n + 1]; Arrays.fill(sum, 0); int[] tot = new int[n + 1]; Arrays.fill(tot, 0); // Precomputing prefix arrays for (int i = 0; i < n; i++) { sum[i + 1] += sum[i]; if (s.charAt(i) == '0') sum[i + 1]++; if (s.charAt(i) == '1') tot[i + 1]++; tot[i + 1] += tot[i]; } // Initializing cnt to count total // number of valid substrings. int cnt = 0; for (int i = k; i <= n; i++) { // Condition for a valid substring if ((tot[i - k] == 0) && (tot[n] - tot[i] == 0) && (sum[i] - sum[i - k] == 0)) // Incrementing cnt to keep // track of valid substrings. cnt++; } // Returning the answer if (cnt == 1) return "Yes"; return "No\n"; } // Driver's code public static void main(String[] args) { String s = "00?1???10?"; int k = 5; // Function Call System.out.println(isValidString(s, k)); }}// This code is contributed by Susobhan Akhuli |
Python3
# Function to check if the given# string is validdef isValidString(s, k): # Getting size of the string n = len(s) # Initializing prefix arrays sum_arr = [0] * (n + 1) tot = [0] * (n + 1) # Precomputing prefix arrays for i in range(n): sum_arr[i + 1] += sum_arr[i] if s[i] == '0': sum_arr[i + 1] += 1 if s[i] == '1': tot[i + 1] += 1 tot[i + 1] += tot[i] # Initializing cnt to count total # number of valid substrings. cnt = 0 for i in range(k, n + 1): # Condition for a valid substring if tot[i - k] == 0 and tot[n] - tot[i] == 0 and sum_arr[i] - sum_arr[i - k] == 0: # Incrementing cnt to keep # track of valid substrings. cnt += 1 # Returning the answer if cnt == 1: return "Yes" return "No\n"# Driver's codeif __name__ == '__main__': s = "00?1???10?" k = 5 # Function Call print(isValidString(s, k))# akashish__ |
C#
// C# program for the above approachusing System;using System.Collections.Generic;public class GFG { // Function to check if the given // string is valid static string IsValidString(string s, int k) { // Getting size of the string int n = s.Length; // Initializing prefix arrays List<int> sum = new List<int>(n + 1); List<int> tot = new List<int>(n + 1); for (int i = 0; i <= n; i++) { sum.Add(0); tot.Add(0); } // Precomputing prefix arrays for (int i = 0; i < n; i++) { sum[i + 1] += sum[i]; if (s[i] == '0') sum[i + 1]++; if (s[i] == '1') tot[i + 1]++; tot[i + 1] += tot[i]; } // Initializing cnt to count total // number of valid substrings. int cnt = 0; for (int i = k; i <= n; i++) { // Condition for a valid substring if (tot[i - k] == 0 && tot[n] - tot[i] == 0 && sum[i] - sum[i - k] == 0) { // Incrementing cnt to keep // track of valid substrings. cnt++; } } // Returning the answer if (cnt == 1) return "Yes"; return "No\n"; } // Driver's code public static void Main() { string s = "00?1???10?"; int k = 5; // Function Call Console.WriteLine(IsValidString(s, k)); }}// This code is contributed by Susobhan Akhuli |
Javascript
// Javascript program for the above approach// Function to check if the given// string is validfunction isValidString(s, k) { // Getting size of the string let n = s.length; // Initializing prefix arrays let sum = Array(n + 1).fill(0); let tot = Array(n + 1).fill(0); // Precomputing prefix arrays for (let i = 0; i < n; i++) { sum[i + 1] += sum[i]; if (s[i] == '0') sum[i + 1]++; if (s[i] == '1') tot[i + 1]++; tot[i + 1] += tot[i]; } // Initializing cnt to count total // number of valid substrings. let cnt = 0; for (let i = k; i <= n; i++) { // Condition for a valid substring if (tot[i - k] == 0 && tot[n] - tot[i] == 0 && sum[i] - sum[i - k] == 0) // Incrementing cnt to keep // track of valid substrings. cnt++; } // Returning the answer if (cnt == 1) return "Yes"; return "No\n";}// Driver's codelet s = "00?1???10?";let k = 5;// Function Callconsole.log(isValidString(s, k));// This code is contributed by Susobhan Akhuli |
Yes
Time Complexity: O(|s|)
Auxiliary Space: O(|s|)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
