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.
Examples :
Input : str = “001”
Output : 1
Minimum number of flips required = 1
We can flip 1st bit from 0 to 1
Input : str = “0001010111”
Output : 2
Minimum number of flips required = 2
We can flip 2nd bit from 0 to 1 and 9th
bit from 1 to 0 to make alternate
string “0101010101”.
Expected time complexity : O(n) where n is length of input string.
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.
Total time complexity of solution will be O(n)
Implementation:
C++
#include <bits/stdc++.h>
using namespace std;
char flip(char ch) { return (ch == '0') ? '1' : '0'; }
int getFlipWithStartingCharcter(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;
}
int minFlipToMakeStringAlternate(string str)
{
return min(getFlipWithStartingCharcter(str, '0'),
getFlipWithStartingCharcter(str, '1'));
}
int main()
{
string str = "0001010111";
cout << minFlipToMakeStringAlternate(str);
return 0;
}
|
C
#include <stdio.h>
#include <string.h>
int min(int num1, int num2)
{
return (num1 > num2) ? num2 : num1;
}
char flip(char ch) { return (ch == '0') ? '1' : '0'; }
int getFlipWithStartingCharcter(char str[], char expected)
{
int flipCount = 0;
for (int i = 0; i < strlen(str); i++) {
if (str[i] != expected)
flipCount++;
expected = flip(expected);
}
return flipCount;
}
int minFlipToMakeStringAlternate(char str[])
{
return min(getFlipWithStartingCharcter(str, '0'),
getFlipWithStartingCharcter(str, '1'));
}
int main()
{
char str[] = "0001010111";
printf("%d",minFlipToMakeStringAlternate(str));
return 0;
}
|
Java
class GFG
{
public static char flip(char ch)
{
return (ch == '0') ? '1' : '0';
}
public static int getFlipWithStartingCharcter(String str,
char expected)
{
int flipCount = 0;
for (int i = 0; i < str.length(); i++)
{
if (str.charAt(i) != expected)
flipCount++;
expected = flip(expected);
}
return flipCount;
}
public static int minFlipToMakeStringAlternate(String str)
{
return Math.min(getFlipWithStartingCharcter(str, '0'),
getFlipWithStartingCharcter(str, '1'));
}
public static void main(String args[])
{
String str = "0001010111";
System.out.println(minFlipToMakeStringAlternate(str));
}
}
|
Python 3
def flip( ch):
return '1' if (ch == '0') else '0'
def getFlipWithStartingCharcter(str, expected):
flipCount = 0
for i in range(len( str)):
if (str[i] != expected):
flipCount += 1
expected = flip(expected)
return flipCount
def minFlipToMakeStringAlternate(str):
return min(getFlipWithStartingCharcter(str, '0'),
getFlipWithStartingCharcter(str, '1'))
if __name__ == "__main__":
str = "0001010111"
print(minFlipToMakeStringAlternate(str))
|
C#
using System;
class GFG
{
public static char flip(char ch)
{
return (ch == '0') ? '1' : '0';
}
public static int getFlipWithStartingCharcter(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;
}
public static int minFlipToMakeStringAlternate(string str)
{
return Math.Min(getFlipWithStartingCharcter(str, '0'),
getFlipWithStartingCharcter(str, '1'));
}
public static void Main()
{
string str = "0001010111";
Console.Write(minFlipToMakeStringAlternate(str));
}
}
|
PHP
<?php
function flip( $ch)
{
return ($ch == '0') ? '1' : '0';
}
function getFlipWithStartingCharcter($str,
$expected)
{
$flipCount = 0;
for ($i = 0; $i < strlen($str); $i++)
{
if ($str[$i] != $expected)
$flipCount++;
$expected = flip($expected);
}
return $flipCount;
}
function minFlipToMakeStringAlternate( $str)
{
return min(getFlipWithStartingCharcter($str, '0'),
getFlipWithStartingCharcter($str, '1'));
}
$str = "0001010111";
echo minFlipToMakeStringAlternate($str);
?>
|
Javascript
<script>
function flip(ch)
{
return (ch == '0') ? '1' : '0';
}
function getFlipWithStartingCharcter(str,expected)
{
let flipCount = 0;
for (let i = 0; i < str.length; i++)
{
if (str.charAt(i) != expected)
flipCount++;
expected = flip(expected);
}
return flipCount;
}
function minFlipToMakeStringAlternate(str)
{
return Math.min(getFlipWithStartingCharcter(str, '0'),
getFlipWithStartingCharcter(str, '1'));
}
let str = "0001010111";
document.write(minFlipToMakeStringAlternate(str));
</script>
|
Time Complexity: O(N)
Auxiliary Space: O(1)
Minimum number of replacements to make the binary string alternating | Set 2
If you like GeeksforGeeks and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.
Feeling lost in the world of random DSA topics, wasting time without progress? It's time for a change! Join our DSA course, where we'll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 geeks!