Problem Statement:
You are given a binary string of 0s and 1s.
You need to find the min number of flips required to make the sequence alternate by flipping some bits
Example
Input : “001”
Output : 1
Here the minimum number of flips required are 1.
If you flip the first bit from “0” to “1”, you will get the string in alternate sequence “101”.
Solution
We can solve this problem by considering all the possibility.
Alternate string starting with 0
And alternate string starting with 1.
Then we take the minimum of them and display the result.
This task will take O(n) time.
Here we loop over all characters of the string and if the character is expected character then we will not do anything else we will flip it and increase the count by 1
This is a bruteforce approach where we get all the possible sequence.
Solution in C++
#include <vector>
#include <algorithm>
//visit www.ProDeveloperTutorial.com for 450+ solved questions
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
// function to flip a character
char flip(char ch)
{
return (ch == '0') ? '1' : '0';
}
// function to flip the characters and get the count
int get_min_number_of_flips_required_with_Starting_character(string str, char expected)
{
int flipCount = 0;
for (int i = 0; i < str.length(); i++)
{
if (str[i] != expected)
flipCount++;
expected = flip(expected);
}
return flipCount;
}
//function to get the min number of flips required.
int min_flip_required_to_make_string_alternate(string str)
{
return min(get_min_number_of_flips_required_with_Starting_character(str, '0'),
get_min_number_of_flips_required_with_Starting_character(str, '1'));
}
int main()
{
string str = "001";
cout << "The min number of flips required are "<< min_flip_required_to_make_string_alternate(str)<<endl;
return 0;
}
Output:
The min number of flips required are 1