## Monday, November 21, 2016

### Number of flips to make binary string alternate - GeeksforGeeks

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 character`
`char` `flip(``char` `ch)`
`{`
`    ``return` `(ch == ``'0'``) ? ``'1'` `: ``'0'``;`
`}`
`//  Utility method to get minimum flips when`
`//  alternate string starts with expected char`
`int` `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 alternate`
`int` `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'``));`
`}`