Minimum operations require to balance Binary String
Given a binary string S of length N, the task is to find the minimum number of operations required to balance (equal number of β0β and β1β) the given binary string, you can perform two types of operations one at a time, which is given below.
- Remove a character from the front of the given string.
- Remove a character from the end of the given string.
Examples:
Input: S = β0111000β
Output: 1
Explanation: Remove 1 character from the front of the given string.Input: S = β11100100β
Output: 0
Approach (Using prefix Sum Technique):
If we assign value -1 to β0β characters and the value of +1 to β1β characters, then any valid substring in which the count of β0βs and β1βs are equal will result in zero sum. Now, the only task is to determine the length of the longest substring whose sum would be zero. The remaining character n β length of the longest substring with 0 sum would be the result.
Steps to solve this problem:
- Create a map unmap to store the prefix sums with their first occurrence indices.
- Iterate through the characters in the string s:
- For each character, update the prefixSum by +1 if the character is β1β, or -1 if the character is β0β.
- If the prefixSum becomes zero at any point, update result by (i + 1), this ensures that this is the longest valid substring encountered so far.
- Check if the current prefixSum value exists in the unmap.
- If true, update result again with the maximum of its current value and i β unmap[prefixSum], which calculates the length of the current valid substring.
- Otherwise, store current prefixSum in unmap with the index i.
- Finally, return the remaining length of the string, which is n β result.
Below is the implementation of the above approach:
C++
// C++ code to implement the approach. #include <bits/stdc++.h> using namespace std; // Function to solve the problem int minOperation(string& s) { // Storing prefixSum with index // of its first occurance unordered_map< int , int > unmap; int n = s.size(); // For storing the prefix Sum // ending at ith index int prefixSum = 0; // For keeping the length of // longest binary string where // number of zero and ones are equal int result = 0; // Iterate over the string for ( int i = 0; i < n; i++) { prefixSum += ((s[i] == '1' ) ? 1 : -1); if (prefixSum == 0) { result = max(result, i + 1); } // Check if prefixSum have // previously occured or not if (unmap.count(prefixSum)) { // Update the result with // this valid substring result = max(result, i - unmap[prefixSum]); } else { // Store this prefixSum has // occur at ith index // in the map. unmap[prefixSum] = i; } } // Return the remaining length // other than the longest // valid substring. return n - result; } // Driver code int main() { string S = "0111000" ; // Function call int result = minOperation(S); cout << result << endl; return 0; } |
Java
import java.util.HashMap; public class Main { // Function to solve the problem public static int minOperation(String s) { // Storing prefixSum with the index of its first // occurrence HashMap<Integer, Integer> unmap = new HashMap<>(); int n = s.length(); // For storing the prefix Sum ending at the ith // index int prefixSum = 0 ; // For keeping the length of the longest binary // string where the number of zeros and ones are // equal int result = 0 ; // Iterate over the string for ( int i = 0 ; i < n; i++) { prefixSum += (s.charAt(i) == '1' ? 1 : - 1 ); if (prefixSum == 0 ) { result = Math.max(result, i + 1 ); } // Check if prefixSum has previously occurred or // not if (unmap.containsKey(prefixSum)) { // Update the result with this valid // substring result = Math.max(result, i - unmap.get(prefixSum)); } else { // Store this prefixSum has occurred at the // ith index in the map. unmap.put(prefixSum, i); } } // Return the remaining length other than the // longest valid substring. return n - result; } // Driver code public static void main(String[] args) { String S = "0111000" ; // Function call int result = minOperation(S); System.out.println(result); } } |
Python3
def minOperation(s): # Storing prefixSum with index # of its first occurrence unmap = {} n = len (s) # For storing the prefix Sum # ending at ith index prefixSum = 0 # For keeping the length of # the longest binary string where # the number of zeros and ones are equal result = 0 # Iterate over the string for i in range (n): if s[i] = = '1' : prefixSum + = 1 else : prefixSum - = 1 if prefixSum = = 0 : result = max (result, i + 1 ) # Check if prefixSum has # previously occurred or not if prefixSum in unmap: # Update the result with # this valid substring result = max (result, i - unmap[prefixSum]) else : # Store this prefixSum has # occurred at ith index # in the map. unmap[prefixSum] = i # Return the remaining length # other than the longest # valid substring. return n - result # Driver code if __name__ = = "__main__" : S = "0111000" # Function call result = minOperation(S) print (result) |
C#
using System; using System.Collections.Generic; class Program { // Function to solve the problem static int MinOperation( string s) { // Storing prefixSum with index // of its first occurrence Dictionary< int , int > unmap = new Dictionary< int , int >(); int n = s.Length; // For storing the prefix Sum // ending at ith index int prefixSum = 0; // For keeping the length of // longest binary string where // number of zero and ones are equal int result = 0; // Iterate over the string for ( int i = 0; i < n; i++) { prefixSum += (s[i] == '1' ) ? 1 : -1; if (prefixSum == 0) { result = Math.Max(result, i + 1); } // Check if prefixSum has // previously occurred or not if (unmap.ContainsKey(prefixSum)) { // Update the result with // this valid substring result = Math.Max(result, i - unmap[prefixSum]); } else { // Store this prefixSum has // occurred at ith index // in the map. unmap[prefixSum] = i; } } // Return the remaining length // other than the longest // valid substring. return n - result; } // Driver code static void Main() { string S = "0111000" ; // Function call int result = MinOperation(S); Console.WriteLine(result); } } |
Javascript
function MinOperation(s) { // Storing prefixSum with index // of its first occurrence let unmap = new Map(); let n = s.length; // For storing the prefix Sum // ending at ith index let prefixSum = 0; // For keeping the length of // longest binary string where // number of zeros and ones are equal let result = 0; // Iterate over the string for (let i = 0; i < n; i++) { prefixSum += (s[i] === '1' ) ? 1 : -1; if (prefixSum === 0) { result = Math.max(result, i + 1); } // Check if prefixSum has // previously occurred or not if (unmap.has(prefixSum)) { // Update the result with // this valid substring result = Math.max(result, i - unmap.get(prefixSum)); } else { // Store this prefixSum has // occurred at ith index // in the map. unmap.set(prefixSum, i); } } // Return the remaining length // other than the longest // valid substring. return n - result; } // Driver code let S = "0111000" ; // Function call let result = MinOperation(S); console.log(result); |
1
Time Complexity: O(N), where N is the length of the given binary string.
Auxiliary Space: O(N)
Contact Us