Minimize replacement of bits to make the count of 01 substring equal to 10 substring
Given a binary string str. The task is to minimize the number of replacements of β0β by β1β or β1β by β0β to balance the binary string. A binary string is said to be balanced: βif the number of β01β substring = number of β10β substringβ.
Examples:
Input: str = β101010β
Output: 1
Explanation: β01β = 2 & β10β = 3. So change the last character to β1β. The modified string will be β101011β or β001010β.Input: str = β0000100β // balanced, β01β = 1 & β10β = 1
Output: 0
Explanation: The string is already balanced.
Approach: One can notice that βthe balanced binary string will always have itβs first character equals to last character of string.β
Only one step is required to balance it, that is s.back() = s.front(). See the proof provided below
Proof:
Above Approach can be proved by using Principle of Mathematical Induction.
NOTE: In below proof, all the cases where first character equals to last character are considered.for n = 0 β> empty string ββ // count of β10β = 0 & count of β01β = 0
for n = 1 β> β0β or β1β // count of β10β = 0 & count of β01β = 0
for n = 2 β> β00β or β11β // count of β10β = 0 & count of β01β = 0
for n = 3β> β000β // count of β10β = 0 & count of β01β = 0
or β111β // count of β10β = 0 & count of β01β = 0
or β010β // count of β10β = 1 & count of β01β = 1
or β101β // count of β10β = 1 & count of β01β = 1Hence, By the principle of mathematical induction it will be true for every n, where n is a natural number.
Below is the implementation of the above approach.
C++
// C++ code to implement above approach #include <bits/stdc++.h> using namespace std; // Function to count the minimum // number of replacements int minimizeReplacements(string str) { unordered_map<string, int > count; string temp; // Loop to count the minimum number // of replacements required for ( int i = 0; i < str.length() - 1; i++) { temp = str.substr(i, 2); count[temp]++; } return abs (count[ "10" ] - count[ "01" ]); } // Driver code int main() { // Given string string str = "101010" ; cout << minimizeReplacements(str) << endl; return 0; } |
Java
// Java code to implement above approach import java.util.HashMap; class GFG{ // Function to count the minimum // number of replacements static int minimizeReplacements(String str) { HashMap<String, Integer> count = new HashMap<String, Integer>(); String temp; // Loop to count the minimum number // of replacements required for ( int i = 0 ; i < str.length() - 1 ; i++) { temp = str.substring(i, i + 2 ); if (count.containsKey(temp)) count.put(temp, count.get(temp) + 1 ); else count.put(temp, 1 ); } return Math.abs(count.get( "10" ) - count.get( "01" )); } // Driver code public static void main(String args[]) { // Given string String str = "101010" ; System.out.print(minimizeReplacements(str)); } } // This code is contributed by gfgking |
Python3
# Python code for the above approach # Function to count the minimum # number of replacements def minimizeReplacements( str ): count = {} temp = "" # Loop to count the minimum number # of replacements required for i in range ( 0 , len ( str ) - 1 ): temp = str [i: i + 2 ] if temp in count: count[temp] = count[temp] + 1 else : count[temp] = 1 return abs (count[ "10" ] - count[ "01" ]) # Driver code # Given string str = "101010" print (minimizeReplacements( str )) # This code is contributed by Potta Lokesh |
C#
// C# code to implement above approach using System; using System.Collections.Generic; class GFG { // Function to count the minimum // number of replacements static int minimizeReplacements( string str) { Dictionary< string , int > count = new Dictionary< string , int >(); string temp; // Loop to count the minimum number // of replacements required for ( int i = 0; i < str.Length - 1; i++) { temp = str.Substring(i, 2); if (count.ContainsKey(temp)) count[temp]++; else count[temp] = 1; } return Math.Abs(count[ "10" ] - count[ "01" ]); } // Driver code public static void Main() { // Given string string str = "101010" ; Console.WriteLine(minimizeReplacements(str)); } } // This code is contributed by ukasp. |
Javascript
<script> // JavaScript code to implement above approach // Function to count the minimum // number of replacements const minimizeReplacements = (str) => { count = {}; let temp = "" ; // Loop to count the minimum number // of replacements required for (let i = 0; i < str.length - 1; i++) { temp = str.substring(i, i + 2); if (temp in count) count[temp]++; else count[temp] = 1; } return Math.abs(count[ "10" ] - count[ "01" ]); } // Driver code // Given string let str = "101010" ; document.write(minimizeReplacements(str)); // This code is contributed by rakeshsahni </script> |
1
Time Complexity: O(N)
Auxiliary Space: O(N), for the map used.
Contact Us