Minimum swaps required to make a binary string alternating
You are given a binary string of even length (2N) and an equal number of 0’s (N) and 1’s (N).
What is the minimum number of swaps to make the string alternating? A binary string is alternating if no two consecutive elements are equal.
Examples:
Input : 000111
Output : 1
Explanation : Swap index 2 and index 5 to get 010101Input : 1010
Output : 0
You may count the numbers of 1’s at odd and even positions or 0’s at odd and even positions in the string. The result would not change because they complete each other.
In the following solution, we will count the 1’s.
- Count the number of ones at the odd positions and even positions of the string. Let their count be odd_1 and even_1 respectively.
- We will always swap a 1 with a 0 (other swaps are pointless). So we need to transfer all the 1s to be only on even positions or only on odd positions. To do so we need min(odd_1, even_1) swaps which is the answer.
This solution Is possible because you are promised that odd_1 + even_1 = N and odd_0 + even_0 = N. also as a result of that we can see that odd_1 + odd_0 = N and even_1 + even_0 = N because on a string of even length there is the same amount of chars in even and odd positions.
Below is the implementation of the above approach:
C++
// CPP implementation of the approach #include <bits/stdc++.h> using namespace std; // returns the minimum number of swaps // of a binary string // passed as the argument // to make it alternating int countMinSwaps(string st) { // counts number of ones at odd // and even positions int odd_1 = 0, even_1 = 0; for ( int i = 0; i < st.length(); i++) { if (st[i] == '1' ) { if (i % 2 == 0) even_1++; else { odd_1++; } } } // calculates the minimum number of swaps return min(odd_1, even_1); } // Driver code int main() { string st = "000111" ; cout << countMinSwaps(st) << endl; return 0; } // This code is contributed by tamircohen2468 |
Java
// Java implementation of the approach class GFG { // returns the minimum number of swaps // of a binary string // passed as the argument // to make it alternating static int countMinSwaps(String st) { // counts number of ones at odd // and even positions int odd_1 = 0 , even_1 = 0 ; for ( int i = 0 ; i < st.length(); i++) { if (st.charAt(i) == '1' ) { if (i % 2 == 0 ) even_1++; else odd_1++; } } // calculates the minimum number of swaps return Math.min(odd_1, even_1); } // Driver code public static void main(String[] args) { String st = "000111" ; System.out.println(countMinSwaps(st)); } } // This code is contributed by tamircohen2468 |
Python3
# Python3 implementation of the # above approach # returns the minimum number of swaps of a binary string # passed as the argument to make it alternating def countMinSwaps(st): # counts number of ones at odd # and even positions odd_1, even_1 = 0 , 0 for i in range ( 0 , len (st)): if st[i] = = "1" : if i % 2 = = 0 : even_1 + = 1 else : odd_1 + = 1 # calculates the minimum number of swaps return min (odd_1, even_1) # Driver code if __name__ = = "__main__" : st = "000111" print (countMinSwaps(st)) # This code is contributed by tamircohen2468 |
C#
// C# implementation of the approach using System; public class GFG { // returns the minimum number of swaps // of a binary string // passed as the argument // to make it alternating public static int countMinSwaps( string st) { // counts number of ones at odd // and even positions int odd_1 = 0, even_1 = 0; for ( int i = 0; i < st.Length; i++) { if (st[i] == '1' ) { if (i % 2 == 0) { even_1++; } else { odd_1++; } } } // calculates the minimum number of swaps return Math.Min(odd_1, even_1); } // Driver code public static void Main( string [] args) { string st = "000111" ; Console.WriteLine(countMinSwaps(st)); } } // This code is contributed by tamircohen2468 |
PHP
<?php // PHP implementation of the approach // returns the minimum number of swaps // of a binary string passed as the // argument to make it alternating function countMinSwaps( $st ) { // counts number of ones at odd // and even positions $odd_1 = 0; $even_1 = 0; for ( $i = 0; $i < strlen ( $st ); $i ++) { if ( $st [ $i ] == '1' ) { if ( $i % 2 == 0) { $even_1 ++; } else { $odd_1 ++; } } } // calculates the minimum number of swaps return min( $odd_1 , $even_1 ); } // Driver code $st = "000111" ; echo (countMinSwaps( $st )); // This code is contributed by tamircohen2468 ?> |
Javascript
<script> // Javascript implementation of the approach // returns the minimum number of swaps // of a binary string // passed as the argument // to make it alternating function countMinSwaps(st) { // counts number of ones at odd // and even positions let odd_1 = 0, even_1 = 0; for (let i = 0; i < st.length; i++) { if (st[i] === '1' ) { if (i % 2 === 0) { even_1++; } else { odd_1++; } } } // calculates the minimum number of swaps return Math.min(odd_1, even_1); } let st = "000111" ; document.write(countMinSwaps(st)); // This code is contributed by tamircohen2468 </script> |
1
Complexity Analysis:
- Time Complexity: O(n) // n is the length of the string
- Auxiliary Complexity: O(1) // since there is no extra array used so constant space is used
Approach for odd and even length string :
Let the string length be N.
In this approach, we will consider three cases :
- The answer is impossible when the total number of ones > the total number of zeroes + 1 or the total number of zeroes > the total number of ones + 1.
- The string is of even length :
We will count the number of ones on odd positions (odd_1) and the number of ones on even positions (even_1) then the answer is min (odd_1, even_1), same as before. - The string is of odd length :
Here we consider two cases :- the total number of ones > total number of zeroes (then we have put ones in even positions) so, the answer is the number of ones at odd positions.
- the total number of zeroes > total number of ones (then we have put zeroes in even positions) so, the answer is the number of zeroes at odd positions.
Implementation:
C++
// C++ implementation of the above approach #include <bits/stdc++.h> using namespace std; // function to count minimum swaps // required to make binary string // alternating int countMinSwaps(string s) { // stores total number of ones int odd_1 = 0, even_1 = 0; // stores total number of zeroes int odd_0 = 0, even_0 = 0; for ( int i = 0; i < s.size(); i++) { if (i % 2 == 0) { if (s[i] == '1' ) { even_1++; } else { even_0++; } } else { if (s[i] == '1' ) { odd_1++; } else { odd_0++; } } } // Total amount of 1's - Total amount of 0's int chars_diff = (odd_1 + even_1) - (odd_0 + even_0); // Even length String if (chars_diff == 0) { return min(odd_1, even_1); } // More 1's the 0's, 1's needs to be on even // positions else if (chars_diff == 1) { return odd_1; } // More 0's the 1's, 0's needs to be on even // positions else if (chars_diff == -1) { return odd_0; } // impossible condition return -1; } // Driver code int main() { string s = "111000" ; cout << countMinSwaps(s); return 0; } // This code is contributed by tamircohen2468 |
Java
// Java implementation of the above approach import java.util.*; class GFG { // function to count minimum swaps // required to make binary String // alternating static int countMinSwaps(String s) { // stores total number of ones int odd_1 = 0 , even_1 = 0 ; // stores total number of zeroes int odd_0 = 0 , even_0 = 0 ; for ( int i = 0 ; i < s.length(); i++) { if (i % 2 == 0 ) { if (s.charAt(i) == '1' ) { even_1++; } else { even_0++; } } else { if (s.charAt(i) == '1' ) { odd_1++; } else { odd_0++; } } } // Total amount of 1's - Total amount of 0's int chars_diff = (odd_1 + even_1) - (odd_0 + even_0); // Even length String if (chars_diff == 0 ) { return Math.min(odd_1, even_1); } // More 1's the 0's, 1's needs to be on even // positions else if (chars_diff == 1 ) { return odd_1; } // More 0's the 1's, 0's needs to be on even // positions else if (chars_diff == - 1 ) { return odd_0; } // impossible condition return - 1 ; } // Driver code public static void main(String[] args) { String s = "111000" ; System.out.print(countMinSwaps(s)); } } // This code is contributed by tamircohen2468 |
Python3
# Python implementation of the above approach # function to count minimum swaps # required to make binary string # alternating def countMinSwaps(s): # stores total number of ones odd_1 = 0 even_1 = 0 # stores total number of zeroes odd_0 = 0 even_0 = 0 for i in range ( len (s)): if i % 2 = = 0 : if s[i] = = '1' : even_1 + = 1 else : even_0 + = 1 else : if s[i] = = '1' : odd_1 + = 1 else : odd_0 + = 1 # Total amount of 1's - Total amount of 0's chars_diff = (odd_1 + even_1) - (odd_0 + even_0) # Even length String if chars_diff = = 0 : return min (odd_1, even_1) # More 1's the 0's, 1's needs to be on even positions elif chars_diff = = 1 : return odd_1 # More 0's the 1's, 0's needs to be on even positions elif chars_diff = = - 1 : return odd_0 # Impossible condition return - 1 if __name__ = = '__main__' : # Driver code s = "111000" print (countMinSwaps(s)) # This code is contributed by tamircohen2468 |
C#
// C# implementation of the above approach using System; class GFG { // Function to count minimum swaps // required to make binary String // alternating static int countMinSwaps( string s) { // stores total number of ones int odd_1 = 0, even_1 = 0; // stores total number of zeroes int odd_0 = 0, even_0 = 0; for ( int i = 0; i < s.Length; i++) { if (i % 2 == 0) { if (s[i] == '1' ) { even_1++; } else { even_0++; } } else { if (s[i] == '1' ) { odd_1++; } else { odd_0++; } } } // Total amount of 1's - Total amount of 0's int chars_diff = (odd_1 + even_1) - (odd_0 + even_0); // Even length String if (chars_diff == 0) { return Math.Min(odd_1, even_1); } // More 1's the 0's, 1's needs to be on even // positions else if (chars_diff == 1) { return odd_1; } // More 0's the 1's, 0's needs to be on even // positions else if (chars_diff == -1) { return odd_0; } // impossible condition return -1; } // Driver code public static void Main(String[] args) { string s = "111000" ; Console.Write(countMinSwaps(s)); } } // This code is contributed by tamircohen2468 |
Javascript
<script> // JavaScript implementation of the above approach // function to count minimum swaps // required to make binary String // alternating function countMinSwaps(s) { // stores total number of ones var odd_1 = 0, even_1 = 0; // stores total number of zeroes var odd_0 = 0, even_0 = 0; for ( var i = 0; i < s.length; i++) { if (i % 2 === 0) { if (s.charAt(i) === '1' ) { even_1++; } else { even_0++; } } else { if (s.charAt(i) === '1' ) { odd_1++; } else { odd_0++; } } } // Total amount of 1's - Total amount of 0's var chars_diff = (odd_1 + even_1) - (odd_0 + even_0); // Even length String if (chars_diff === 0) { return Math.min(odd_1, even_1); } // More 1's the 0's, 1's needs to be on even // positions else if (chars_diff === 1) { return odd_1; } // More 0's the 1's, 0's needs to be on even // positions else if (chars_diff === -1) { return odd_0; } // impossible condition return -1; } // Driver code var s = "111000" ; document.write(countMinSwaps(s)); // This code is contributed by tamircohen2468 </script> |
1
complexity Analysis:
- Time Complexity: O(N)
- Auxiliary Complexity: O(1)