Given a binary string S having N characters and two integers K and Q, the task is to find the minimum number of remaining zeroes after at most Q operations, such that in each operation, choose any substring of size at most K and change all its elements to 1.
Example:
Input: S = 000111, K = 2, Q = 1
Output: 1
Explanation:
Choose the substring S[0, 1] and change all the characters to 1. The final string will be 110111 that has 1 zero remaining which is the minimum possible.Input: S = 0100010110, K = 3, Q = 2
Output: 2
Approach 1: Memoisation
We can define dp[i][j] as the minimum number of zeroes in S[0:i] after j operations. We can then derive the recurrence relation using the following steps:
- If K = 0 or Q = 0, we cannot perform any operations, so the answer is simply the number of zeroes in the original string.
- If Q is large enough such that we can perform operations on all substrings of length at most K, then we can simply set the answer to 0.
- Initialize dp[0][j] = 0 for all j, since there are no characters in S[0:0] and we have not performed any operations yet.
- Initialize dp[i][0] = dp[i-1][0] + (S[i-1] == ‘0’) for all i, since the minimum number of zeroes in S[0:i] after 0 operations is simply the minimum number of zeroes in S[0:i-1] plus 1 if the i-th character is ‘0’.
- For all i in the range [1, N] and for all j in the range [1, Q], we can use the following recurrence relation to compute dp[i][j]:
dp[i][j] = min(dp[i-k][j-1], dp[i-1][j] + (S[i-1] == '0')), where k = min(i, K).
The intuition behind this recurrence relation is that we can either perform an operation on the last K characters of S[0:i] (if i >= K) or on all the characters in S[0:i] except for the last character (if i < K). If we perform an operation on the last K characters, then we can reduce the number of zeroes in those characters by 1, and the remaining number of zeroes in S[0:i] is simply dp[i-k][j-1]. Otherwise, if we do not perform an operation on the last K characters, then the remaining number of zeroes in S[0:i] is simply dp[i-1][j] plus 1 if the i-th character is ‘0’.
The final answer is dp[N][Q].
Algorithm:
- Define a function ‘minZeroes‘ that takes the binary string S, a 2D vector ‘dp‘, integers N, K and Q as input parameters.
- Check for the base cases:
a. If k or q is 0, then return the count of 0’s in the string.
b. If q is greater than or equal to the maximum possible number of operations, return 0.
c. If the result for current parameters is already calculated, return it from the memoization table. - If the result is not present in the memoization table, then use the recurrence relation given below to calculate the minimum number of remaining zeroes:
dp[n][q] = min(minZeroes(s, dp, n – 1, k, q) + (s[n – 1] == ‘0’), minZeroes(s, dp, max(n – k, 0), k, q – 1)). - Store the calculated result in the memoization table.
- Return the calculated result.
- In the main function:
a. Define the input parameters S, N, K, and Q.
b. Create a 2D vector ‘dp‘ of size (N+1)x(Q+1), initialized with -1.
c. Call the ‘minZeroes‘ function with the input parameters S, dp, N, K, and Q.
d. Print the result.
Below is the implementation of the above approach:
C++
// C++ code for the approach#include <bits/stdc++.h>using namespace std;// Function to calculate the minimum number of remaining// zeroes in the binary stringint minZeroes(string s, vector<vector<int> >& dp, int n, int k, int q){ // Base cases if (k == 0 || q == 0) { return count( // Count the number of 0s in the string s.begin(), s.end(), '0'); } // If q is greater than or equal to the // maximum possible number of operations, // then no 0s will remain if (q >= (n + k - 1) / k) { return 0; } // If the result for current // parameters is already // calculated, return it from the // memoization table if (dp[n][q] != -1) { return dp[n][q]; } // Recurrence relation to calculate the minimum number // of remaining zeroes dp[n][q] = min( minZeroes(s, dp, n - 1, k, q) + (s[n - 1] == '0'), minZeroes(s, dp, max(n - k, 0), k, q - 1)); // Return the calculated result return dp[n][q];}// Driver's codeint main(){ string S = "0100010110"; int N = S.size(); int K = 3, Q = 2; // 2D vector to store the dp states, // initially having all the values // as INT_MAX vector<vector<int> > dp(N + 1, vector<int>(Q + 1, -1)); // Call the function to calculate // the minimum number of remaining // zeroes and print the result cout << minZeroes(S, dp, N, K, Q); return 0;} |
Java
import java.util.Arrays;public class Main { // Function to calculate the minimum number of remaining // zeroes in the binary string static int minZeroes(String s, int[][] dp, int n, int k, int q) { // Base cases if (k == 0 || q == 0) { return (int) s.chars().filter(ch -> ch == '0').count(); } // If q is greater than or equal to the // maximum possible number of operations, // then no 0s will remain if (q >= (n + k - 1) / k) { return 0; } // If the result for current // parameters is already // calculated, return it from the // memoization table if (dp[n][q] != -1) { return dp[n][q]; } // Recurrence relation to calculate the minimum number // of remaining zeroes dp[n][q] = Math.min( minZeroes(s, dp, n - 1, k, q) + (s.charAt(n - 1) == '0' ? 1 : 0), minZeroes(s, dp, Math.max(n - k, 0), k, q - 1) ); // Return the calculated result return dp[n][q]; } // Driver's code public static void main(String[] args) { String S = "0100010110"; int N = S.length(); int K = 3, Q = 2; // 2D array to store the dp states, // initially having all the values // as -1 int[][] dp = new int[N + 1][Q + 1]; for (int[] row : dp) { Arrays.fill(row, -1); } // Call the function to calculate // the minimum number of remaining // zeroes and print the result System.out.println(minZeroes(S, dp, N, K, Q)); }} |
Python
def min_zeroes(s, dp, n, k, q): # Base cases if k == 0 or q == 0: return s.count('0') # If q is greater than or equal to the # maximum possible number of operations, # then no 0s will remain if q >= (n + k - 1) // k: return 0 # If the result for current # parameters is already # calculated, return it from the # memoization table if dp[n][q] != -1: return dp[n][q] # Recurrence relation to calculate the minimum number # of remaining zeroes dp[n][q] = min( min_zeroes(s, dp, n - 1, k, q) + (1 if s[n - 1] == '0' else 0), min_zeroes(s, dp, max(n - k, 0), k, q - 1) ) # Return the calculated result return dp[n][q]# Driver's codeif __name__ == "__main__": S = "0100010110" N = len(S) K, Q = 3, 2 # 2D array to store the dp states, # initially having all the values # as -1 dp = [[-1] * (Q + 1) for _ in range(N + 1)] # Call the function to calculate # the minimum number of remaining # zeroes and print the result print(min_zeroes(S, dp, N, K, Q)) |
C#
using System;public class MinZeroes { public static int MinZeroesCount(string s, int n, int k, int q) { int[, ] dp = new int[n + 1, q + 1]; // Base case 1: If k or q is 0, return the count of // '0's in the string. if (k == 0 || q == 0) { return s.Split('0').Length - 1; } // Base case 2: If q is greater than or equal to the // maximum possible number of operations, return 0. if (q >= (n + k - 1) / k) { return 0; } // Initialize dp[i][0] for all i. for (int i = 1; i <= n; i++) { dp[i, 0] = dp[i - 1, 0] + (s[i - 1] == '0' ? 1 : 0); } // Fill in the dp table using the recurrence // relation. for (int i = 1; i <= n; i++) { for (int j = 1; j <= q; j++) { int minZeroes = int.MaxValue; for (int x = 1; x <= Math.Min(i, k); x++) { minZeroes = Math.Min(minZeroes, dp[i - x, j - 1]); } dp[i, j] = Math.Min( minZeroes, dp[i - 1, j] + (s[i - 1] == '0' ? 1 : 0)); } } return dp[n, q]; } public static void Main(string[] args) { string S = "0100010110"; int N = S.Length; int K = 3; int Q = 2; int result = MinZeroesCount(S, N, K, Q); Console.WriteLine( "Minimum number of remaining zeroes: " + result); }} |
Javascript
// Function to calculate the minimum number of remaining// zeroes in the binary stringfunction minZeroes(s, dp, n, k, q) { // Base cases if (k === 0 || q === 0) { return s.split('0').length - 1; } // If q is greater than or equal to the // maximum possible number of operations, // then no 0s will remain if (q >= Math.ceil(n / k)) { return 0; } // If the result for current parameters is already // calculated, return it from the memoization table if (dp[n][q] !== -1) { return dp[n][q]; } // Recurrence relation to calculate the minimum number // of remaining zeroes dp[n][q] = Math.min( minZeroes(s, dp, n - 1, k, q) + (s[n - 1] === '0' ? 1 : 0), minZeroes(s, dp, Math.max(n - k, 0), k, q - 1) ); // Return the calculated result return dp[n][q];}// Driver's codeconst S = "0100010110";const N = S.length;const K = 3;const Q = 2;// 2D array to store the dp states,// initially having all the values// as Infinityconst dp = new Array(N + 1);for (let i = 0; i <= N; i++) { dp[i] = new Array(Q + 1).fill(-1);}// Call the function to calculate// the minimum number of remaining// zeroes and print the resultconsole.log(minZeroes(S, dp, N, K, Q));// This code is contributed by akshitaguprzj3 |
Output
2
Time Complexity: O(N*Q) where N is size of input string and Q is number of operations. This is because for each i and j, the function dp(i, j) makes at most two recursive calls and each call takes constant time. Therefore, the number of unique function calls made by the algorithm is bounded by N*Q, and each call takes constant time. Hence, the overall time complexity is O(N*Q).
Auxiliary Space: O(N * Q), which is used to store the values of the subproblems in the 2D DP table. Here N is size of input string and Q is number of operations.
Approach 2: Using Dynamic Programming
Steps:
- Create a 2D array dp[][], where dp[i][j] represents the minimum number of zeroes in the prefix of length i of the given string after j operations. Below are the steps to follow:
- Initially, for all values of j in range [0, Q], dp[0][j] = 0 and for all values of i in range [0, N], dp[i][0] = count of 0 in prefix of length i.
- For each stated dp[i][j], there are two possible choices of operations:
- Perform an operation on the substring S[i – K, i]. In such cases, dp[i][j] = dp[i – K][j – 1].
- Do not perform any operation. In such cases, dp[i][j] = dp[i – 1][j] + X, where the value of X is 1 if the value of S[i – 1] = 0, Otherwise, X = 0.
- Therefore, the DP relation of the above problem can be stated as:
dp[i][j] = min(dp[i – k][j – 1], dp[i – 1][j] + (S[i – 1] == ‘0’)), for all i in the range [1, N] and for all j in the range [1, Q].
5. After completing the steps, the value stored at dp[N][Q] is the required answer.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the minimum number of// zeroes after changing the value of all// elements of any substring of at most K// elements to 1 at most Q number of timesint minZeroeCount(string S, int K, int Q){ // Stores the size of the given string int N = S.size(); // If no operation is possible, return // the count of 0 in the initial string if (K == 0 || Q == 0) { return count(S.begin(), S.end(), '0'); } // If all the elements of the given string // can be selected in Q operations if (Q >= ceil((float)N / K)) { return 0; } // 2D vector to store the dp states, // initially having all the values // as INT_MAX vector<vector<int> > dp(N + 1, vector<int>(Q + 1, INT_MAX)); // Loop to initialize dp[0][j] = 0 // for all j in the range [0, Q], for (int j = 0; j <= Q; ++j) { dp[0][j] = 0; } // Loop to initialize dp[0][j] = count // of 0 in prefix of length i for all // i in the range [1, N], for (int i = 1; i <= N; ++i) { dp[i][0] = dp[i - 1][0] + (S[i - 1] == '0'); } // Traverse over all dp[][] states for (int i = 1; i <= N; ++i) { for (int j = 1; j <= Q; ++j) { // Find the value of dp[i][j] dp[i][j] = min(dp[max(0, i - K)][j - 1], dp[i - 1][j] + (S[i - 1] == '0')); } } // Return answer return dp[N][Q];}// Driver Codeint main(){ string S = "0100010110"; int K = 3; int Q = 2; cout << minZeroeCount(S, K, Q); return 0;} |
Java
// Java program for the above approachimport java.io.*;class GFG { // Function to find the minimum number of // zeroes after changing the value of all // elements of any substring of at most K // elements to 1 at most Q number of times static int minZeroeCount(String S, int K, int Q) { // Stores the size of the given string int N = S.length(); // If no operation is possible, return // the count of 0 in the initial string if (K == 0 || Q == 0) { int c = 0; for(int i = 0; i < S.length(); i++) { if(S.charAt(i) == '0') c++; } return c; } // If all the elements of the given string // can be selected in Q operations if (Q >= Math.ceil((float)N / K)) { return 0; } // 2D vector to store the dp states, // initially having all the values // as INT_MAX int[][] dp = new int[N + 1][Q + 1]; // Loop to initialize dp[0][j] = 0 // for all j in the range [0, Q], for (int j = 0; j <= Q; ++j) { dp[0][j] = 0; } // Loop to initialize dp[0][j] = count // of 0 in prefix of length i for all // i in the range [1, N], for (int i = 1; i <= N; ++i) { if (S.charAt(i - 1) == '0') dp[i][0] = dp[i - 1][0] + 1; else dp[i][0] = dp[i - 1][0]; } // Traverse over all dp[][] states for (int i = 1; i <= N; ++i) { for (int j = 1; j <= Q; ++j) { // Find the value of dp[i][j] if (S.charAt(i - 1) == '0') dp[i][j] = Math.min( dp[(Math.max(0, i - K))][j - 1], dp[i - 1][j] + 1); else dp[i][j] = Math.min( dp[(Math.max(0, i - K))][j - 1], dp[i - 1][j]); } } // Return answer return dp[N][Q]; } // Driver Code public static void main (String[] args) { String S = "0100010110"; int K = 3; int Q = 2; System.out.println(minZeroeCount(S, K, Q)); }}// This code is contributed by Dharanendra L V. |
Python3
# Python 3 program for the above approachimport sysdef cnt(s,ch): count = 0 for x in s: if x == ch: count += 1 return count# Function to find the minimum number of# zeroes after changing the value of all# elements of any substring of at most K# elements to 1 at most Q number of timesdef minZeroeCount(S, K, Q): # Stores the size of the given string N = len(S) # If no operation is possible, return # the count of 0 in the initial string if (K == 0 or Q == 0): return cnt(S,'0') # If all the elements of the given string # can be selected in Q operations if (Q >= int(N/K) + 1): return 0 # 2D vector to store the dp states, # initially having all the values # as INT_MAX dp = [[sys.maxsize for i in range(Q + 1)] for j in range(N + 1)] # Loop to initialize dp[0][j] = 0 # for all j in the range [0, Q], for j in range(Q + 1): dp[0][j] = 0 # Loop to initialize dp[0][j] = count # of 0 in prefix of length i for all # i in the range [1, N], for i in range(1,N+1,1): dp[i][0] = dp[i - 1][0] + (S[i - 1] == '0') # Traverse over all dp[][] states for i in range(1, N + 1, 1): for j in range(1, Q + 1, 1): # Find the value of dp[i][j] dp[i][j] = min(dp[max(0, i - K)][j - 1], dp[i - 1][j]+(S[i - 1] == '0')) # Return answer return dp[N][Q]# Driver Codeif __name__ == '__main__': S = "0100010110" K = 3 Q = 2 print(minZeroeCount(S, K, Q)) # This code is contributed by SURENDRA_GANGWAR. |
C#
// C# program for the above approachusing System;using System.Linq;class GFG { // Function to find the minimum number of // zeroes after changing the value of all // elements of any substring of at most K // elements to 1 at most Q number of times static int minZeroeCount(string S, int K, int Q) { // Stores the size of the given string int N = S.Length; // If no operation is possible, return // the count of 0 in the initial string if (K == 0 || Q == 0) { return S.Count(c => c == '0'); } // If all the elements of the given string // can be selected in Q operations if (Q >= Math.Ceiling((float)N / K)) { return 0; } // 2D vector to store the dp states, // initially having all the values // as INT_MAX int[, ] dp = new int[N + 1, Q + 1]; // Loop to initialize dp[0][j] = 0 // for all j in the range [0, Q], for (int j = 0; j <= Q; ++j) { dp[0, j] = 0; } // Loop to initialize dp[0][j] = count // of 0 in prefix of length i for all // i in the range [1, N], for (int i = 1; i <= N; ++i) { if (S[i - 1] == '0') dp[i, 0] = dp[i - 1, 0] + 1; else dp[i, 0] = dp[i - 1, 0]; } // Traverse over all dp[][] states for (int i = 1; i <= N; ++i) { for (int j = 1; j <= Q; ++j) { // Find the value of dp[i][j] if (S[i - 1] == '0') dp[i, j] = Math.Min( dp[(Math.Max(0, i - K)), j - 1], dp[i - 1, j] + 1); else dp[i, j] = Math.Min( dp[(Math.Max(0, i - K)), j - 1], dp[i - 1, j]); } } // Return answer return dp[N, Q]; } // Driver Code public static void Main() { string S = "0100010110"; int K = 3; int Q = 2; Console.WriteLine(minZeroeCount(S, K, Q)); }}// This code is contributed by ukasp. |
Javascript
<script> // JavaScript program for the above approach const INT_MAX = 2147483647; // Function to find the minimum number of // zeroes after changing the value of all // elements of any substring of at most K // elements to 1 at most Q number of times const minZeroeCount = (S, K, Q) => { // Stores the size of the given string let N = S.length; // If no operation is possible, return // the count of 0 in the initial string if (K == 0 || Q == 0) { let cnt0 = 0; for (let i = 0; i < N; ++i) { if (S[i] == '0') cnt0++; } return cnt0; } // If all the elements of the given string // can be selected in Q operations if (Q >= Math.ceil(N / K)) { return 0; } // 2D vector to store the dp states, // initially having all the values // as INT_MAX const dp = new Array(N + 1).fill(INT_MAX).map(() => new Array(Q + 1).fill(INT_MAX)); // Loop to initialize dp[0][j] = 0 // for all j in the range [0, Q], for (let j = 0; j <= Q; ++j) { dp[0][j] = 0; } // Loop to initialize dp[0][j] = count // of 0 in prefix of length i for all // i in the range [1, N], for (let i = 1; i <= N; ++i) { dp[i][0] = dp[i - 1][0] + (S[i - 1] == '0'); } // Traverse over all dp[][] states for (let i = 1; i <= N; ++i) { for (let j = 1; j <= Q; ++j) { // Find the value of dp[i][j] dp[i][j] = Math.min(dp[(Math.max(0, i - K))][j - 1], dp[i - 1][j] + (S[i - 1] == '0')); } } // Return answer return dp[N][Q]; } // Driver Code let S = "0100010110"; let K = 3; let Q = 2; document.write(minZeroeCount(S, K, Q)); // This code is contributed by rakeshsahni</script> |
Output
2
Time Complexity: O(N*Q)
Auxiliary Space: O(N*Q)
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!
