You are given a binary string S of size N consisting of characters 0 and/or 1. You may remove several characters from the beginning or the end of the string. The task is to find the cost of removal where the cost is the maximum of the following two values:
- The number of characters 0 left in the string.
- The number of characters 1 removed from the string.
Examples:
Input: S = “101110110”
Output: 1
Explanation: It is possible to remove two characters from the beginning and one character from the end. Only one 1 is deleted, only one 0 remains. So the cost is 1Input: S = “1001001001001”
Output: 3
Explanation: It is possible to remove three characters from the beginning and six characters from the end. Two 0 remains, three 1 are deleted. So the cost is 3Input: S = “0000111111”
Output: 0
Explanation: It is optimal to remove four characters from the beginning.Input: S = “00000”
Output: 0
Explanation: It is optimal to remove the whole string.
Approach: The problem can be solved based on the following idea:
Say there are total X number of 0s in S. So if we do not delete any of the characters the maximum cost will be X. We have to delete some 0 to minimize the cost.
The optimal way is to delete at most X elements in total. If we delete more than X elements, there is a possibility of deleting more than X 1s which will result in more cost. Also we cannot reduce the cost by deleting more than X characters.
Proof: Say there were Y 1s deleted among the total X deleted characters. Now to reduce the cost we can only delete 0s from the string. There can at max be Y 0s that are not deleted from the string. So the present cost is max(Y, Y) = Y. If we delete those Y then no 0 will be left but already Y 1s are deleted. So the cost will be max(0, Y) = Y.
Follow the below steps to implement the idea efficiently:
- Iterate the string and find the total count of 0s (say count0).
- Maintain the prefix count of zero and suffix count of zeroes in two arrays (say prefixCountZero[] and suffixCountZero[]).
- Iterate from zero to count0 and calculate the current cost as:
- currentCost = count0 – prefixCountZero [ i – 1 ] – suffixCountZero [ n – ( count0 – i ) ]
- The minimum of all values of currentCost will be the answer.
Below is the implementation of the above approach:
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to find the minimum costint minCost(string s){ int n = s.length(); int count0 = 0; int ans = INT_MAX; for (int i = 0; i < n; i++) { if (s[i] == '0') count0++; } vector<int> prefixCountZero(n, 0); vector<int> suffixCountZero(n, 0); // Loop to find the prefix count of 0 for (int i = 0; i < n; i++) { if (i != 0) prefixCountZero[i] = prefixCountZero[i - 1]; if (s[i] == '0') prefixCountZero[i]++; } // Loop to find the suffix count of 0 for (int i = n - 1; i >= 0; i--) { if (i != n - 1) suffixCountZero[i] = suffixCountZero[i + 1]; if (s[i] == '0') suffixCountZero[i]++; } // Loop to find the minimum cost for (int i = 0; i <= count0; i++) { int x; if (i == 0) { x = count0 - suffixCountZero[n - count0]; } else if (i == count0) { x = count0 - prefixCountZero[count0 - 1]; } else { x = count0 - prefixCountZero[i - 1] - suffixCountZero[n - (count0 - i)]; } ans = min(ans, x); } return ans;}// Driver codeint main(){ string S = "101110110"; // Function call cout << minCost(S); return 0;} |
Java
// Java code to implement the approachimport java.io.*;class GFG { // Function to find the minimum cost public static int minCost(String s) { int n = s.length(); int count0 = 0; int ans = Integer.MAX_VALUE; for (int i = 0; i < n; i++) { if (s.charAt(i) == '0') count0++; } int prefixCountZero[] = new int[n]; int suffixCountZero[] = new int[n]; // Loop to find the prefix count of 0s for (int i = 0; i < n; i++) { if (i != 0) prefixCountZero[i] = prefixCountZero[i - 1]; if (s.charAt(i) == '0') prefixCountZero[i]++; } // Loop to find the suffix count of 0s for (int i = n - 1; i >= 0; i--) { if (i != n - 1) suffixCountZero[i] = suffixCountZero[i + 1]; if (s.charAt(i) == '0') suffixCountZero[i]++; } // Loop to find the minimum cost for (int i = 0; i <= count0; i++) { int x; if (i == 0) { x = count0 - suffixCountZero[n - count0]; } else if (i == count0) { x = count0 - prefixCountZero[count0 - 1]; } else { x = count0 - prefixCountZero[i - 1] - suffixCountZero[n - (count0 - i)]; } ans = Math.min(ans, x); } return ans; } // Driver code public static void main(String[] args) { String S = "101110110"; // Function call System.out.println(minCost(S)); }} |
Python3
# Python code to implement the approach# Function to find the minimum costdef minCost(s): n = len(s) count0 = 0 ans = float('inf') for i in range(n): if(s[i] == '0'): count0 += 1 prefixCountZero = [0]*n suffixCountZero = [0]*n # Loop to find the prefix count of 0 for i in range(n): if(i != 0): prefixCountZero[i] = prefixCountZero[i-1] if(s[i] == '0'): prefixCountZero[i] += 1 # Loop to find the suffix count of 0 for i in range(n-1, -1, -1): if(i != n-1): suffixCountZero[i] = suffixCountZero[i+1] if(s[i] == '0'): suffixCountZero[i] += 1 # Loop to find the minimum cost for i in range(count0+1): if(i == 0): x = count0 - suffixCountZero[n - count0] elif(i == count0): x = count0 - prefixCountZero[count0 - 1] else: x = count0 - prefixCountZero[i-1] - suffixCountZero[n-(count0 - i)] ans = min(ans, x) return ansS = "101110110"# Function callprint(minCost(S))# This code is contributed by lokeshmvs21. |
C#
// C# code to implement the approachusing System;public class GFG { // Function to find the minimum cost public static int minCost(String s) { int n = s.Length; int count0 = 0; int ans = Int32.MaxValue; for (int i = 0; i < n; i++) { if (s[i] == '0') count0++; } int[] prefixCountZero = new int[n]; int[] suffixCountZero = new int[n]; // Loop to find the prefix count of 0s for (int i = 0; i < n; i++) { if (i != 0) prefixCountZero[i] = prefixCountZero[i - 1]; if (s[i] == '0') prefixCountZero[i]++; } // Loop to find the suffix count of 0s for (int i = n - 1; i >= 0; i--) { if (i != n - 1) suffixCountZero[i] = suffixCountZero[i + 1]; if (s[i] == '0') suffixCountZero[i]++; } // Loop to find the minimum cost for (int i = 0; i <= count0; i++) { int x; if (i == 0) { x = count0 - suffixCountZero[n - count0]; } else if (i == count0) { x = count0 - prefixCountZero[count0 - 1]; } else { x = count0 - prefixCountZero[i - 1] - suffixCountZero[n - (count0 - i)]; } ans = Math.Min(ans, x); } return ans; } // Driver Code static public void Main() { String S = "101110110"; // Function call Console.WriteLine(minCost(S)); }}// This code is contributed by Rohit Pradhan |
Javascript
// JavaScript code for the above approach // Function to find the minimum cost function minCost(s) { let n = s.length; let count0 = 0; let ans = Number.MAX_VALUE; for (let i = 0; i < n; i++) { if (s[i] == '0') count0++; } let prefixCountZero = new Array(n).fill(0); let suffixCountZero = new Array(n).fill(0); // Loop to find the prefix count of 0 for (let i = 0; i < n; i++) { if (i != 0) prefixCountZero[i] = prefixCountZero[i - 1]; if (s[i] == '0') prefixCountZero[i]++; } // Loop to find the suffix count of 0 for (let i = n - 1; i >= 0; i--) { if (i != n - 1) suffixCountZero[i] = suffixCountZero[i + 1]; if (s[i] == '0') suffixCountZero[i]++; } // Loop to find the minimum cost for (let i = 0; i <= count0; i++) { let x; if (i == 0) { x = count0 - suffixCountZero[n - count0]; } else if (i == count0) { x = count0 - prefixCountZero[count0 - 1]; } else { x = count0 - prefixCountZero[i - 1] - suffixCountZero[n - (count0 - i)]; } ans = Math.min(ans, x); } return ans; } // Driver code let S = "101110110"; // Function call console.log(minCost(S));// This code is contributed by Potta Lokesh |
1
Time Complexity: O(N)
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
