Problem Statement:
You are given a binary string of 0s and 1s. You need to get the minimum steps to make the string alternating.
Example
Input: s = "111000" Output: 1 Swap elements at s[1] and s[4] to make the string alternating.
Solution
In the solution, we count the number of characters that are misplaced and return the count.
Solution in C++
#include <algorithm> //visit www.ProDeveloperTutorial.com for 450+ solved questions #include <iostream> #include <string> #include <stack> #include <vector> #include <unordered_map> #include <queue> using namespace std; int min_fill_pos(string& s, char ch, int current = 0) { int count = 0; for(int i=0; i<s.size(); i+=2) { if(s[i] != ch) count++; } return count; } int min_swaps_required(string s) { //check if the difference between 1s and 0s is greater than 1 int oneCount = count(s.begin(), s.end(), '1'); int zeroCount = count(s.begin(), s.end(), '0'); if(abs(oneCount-zeroCount) > 1) return -1; // if 1s count is greater than 0, check the misplaced character count // for ex: 011. Here 1s > 0s count. // only possible solution is 101. So, starting from 0th index, check // for misplaced character at every i+2th position. // same for 0 if(oneCount > zeroCount) return min_fill_pos(s,'1'); if(zeroCount > oneCount) return min_fill_pos(s,'0'); return min(min_fill_pos(s,'0'), min_fill_pos(s,'1')); } int main() { string s1 = "111000"; cout<<"The min swaps required are "<<min_swaps_required(s1)<<endl; return 0; }
Output:
The min swaps required are 1