Number of flips to make binary string alternate - GeeksforGeeks
Given a binary string, that is it contains only 0s and 1s. We need to make this string a sequence of alternate characters by flipping some of the bits, our goal is to minimize the number of bits to be flipped.
We can solve this problem by considering all possible results, As we are supposed to get alternate string, there are only 2 possibilities, alternate string starting with 0 and alternate string starting with 1. We will try both cases and choose the string which will require minimum number of flips as our final answer.
Trying a case requires O(n) time in which we will loop over all characters of given string, if current character is expected character according to alternation then we will do nothing otherwise we will increase flip count by 1. After trying strings starting with 0 and starting with 1, we will choose the string with minimum flip count.
Read full article from Number of flips to make binary string alternate - GeeksforGeeks
Given a binary string, that is it contains only 0s and 1s. We need to make this string a sequence of alternate characters by flipping some of the bits, our goal is to minimize the number of bits to be flipped.
We can solve this problem by considering all possible results, As we are supposed to get alternate string, there are only 2 possibilities, alternate string starting with 0 and alternate string starting with 1. We will try both cases and choose the string which will require minimum number of flips as our final answer.
Trying a case requires O(n) time in which we will loop over all characters of given string, if current character is expected character according to alternation then we will do nothing otherwise we will increase flip count by 1. After trying strings starting with 0 and starting with 1, we will choose the string with minimum flip count.
// Utility method to flip a characterchar flip(char ch){ return (ch == '0') ? '1' : '0';}// Utility method to get minimum flips when// alternate string starts with expected charint getFlipWithStartingCharcter(string str, char expected){ int flipCount = 0; for (int i = 0; i < str.length(); i++) { // if current character is not expected, // increase flip count if (str[i] != expected) flipCount++; // flip expected character each time expected = flip(expected); } return flipCount;}// method return minimum flip to make binary// string alternateint minFlipToMakeStringAlternate(string str){ // return minimum of following two // 1) flips when alternate strign starts with 0 // 2) flips when alternate strign starts with 1 return min(getFlipWithStartingCharcter(str, '0'), getFlipWithStartingCharcter(str, '1'));}