# Flip or Compress FLIPCOMP Solution Codechef

## Flip or Compress FLIPCOMP Solution

You are given a binary string S. You can perform the following operations on S:

• Flip: Pick an index i (1≤i≤|S|) and flip the i-th character (i.e change 1 to 0 or 0 to 1). For e.g. 011–001→010–001
• Compress: Pick any non-empty substring consisting of the same character and replace it with a single occurrence of that character. For e.g. 1001111–––––10→1001–10

You want to make all the characters of the binary string equal (i.e. either all characters are 0 or all characters are 1). Find the minimum number of operations required to do so.

Input Format

• The first line of input contains a single integer T, denoting the number of test cases. The description of T test cases follows.
• The first and only line of each test case contains a binary string S.

Output Format

For each test case, output a single line containing one integer the minimum number of operations required to make all the characters of S equal.

Constraints

• 1≤T≤105
• 1≤|S|≤106
• S is a binary string.
• It is guaranteed that the sum of |S| over all test cases does not exceed 106.

• 1≤T≤103
• 1≤|S|≤10

• 1≤T≤103
• 1≤|S|≤50

• Original constraints

Sample Input 1

``````3
100011
1110011
000101110``````

Sample Output 1

``````2
2
3``````

Explanation

In the first test case,

• 1000––––11−→−−−−compress 10–11
• 10–11−→−flip 11–11

In the second test case,

• 1110–011−→−flip 1111–011
• 11110–11−→−flip 11111–11

In the third test case,

• 00010–1110−→−flip 00011–1110
• 00011111––––––0−→−−−−compress 0001–0
• 0001–0−→−flip 0000–0

### SOLUTION

Program Python: Flip or Compress FLIPCOMP Solution in Python

``````# cook your dish here
for _ in range(int(input())):
s=input()
v,ans,n=0,0,len(s)
i=0
flag=flag2=False
while i<n:
if s[i]=='0':
if not flag:
flag=True
else:
if not flag2:
flag2=True
else:
if flag:
if flag2:
if i<n-1:
if s[i+1]=='0':
ans+=1
else:
ans+=2
flag=False
flag2=False
else:
ans+=2
flag=False
flag2=False
else:
ans+=1
flag=False
i+=1
if flag:
if flag2:
ans+=2
else:
ans+=1
v=ans
ans=0
i=0
flag=flag2=False
while i<n:
if s[i]=='1':
if not flag:
flag=True
else:
if not flag2:
flag2=True
else:
if flag:
if flag2:
if i<n-1:
if s[i+1]=='1':
ans+=1
else:
ans+=2
flag=False
flag2=False
else:
ans+=2
flag=False
flag2=False
else:
ans+=1
flag=False

i+=1
if flag:
if flag2:
ans+=2
else:
ans+=1
v=min(v,ans)
print(v)``````

Program C++: Flip or Compress FLIPCOMP Solution in C++

``````#include <iostream>
using namespace std;
int main() {
int t; cin >> t;

while(t--){
string s; cin >> s;

int zer = 0;
string sd = s;
for(int i=1; i+1<s.length(); i++){
if(sd[i]=='1' && sd[i-1]=='0' && sd[i+1]=='0' && ((i-2>=0 && sd[i-2]=='0') || (i+2<s.length() && sd[i+2]=='0'))){
zer++;
sd[i] = '0';
}
}

for(int i=0; i<s.length(); i++){
if(sd[i]=='0' && i>1 && sd[i-1]=='0' && sd[i-2]=='0')continue;
else if(sd[i]=='0' && i>0 && sd[i-1]=='0')zer++;
else if(sd[i]=='0')zer++;
}

int one = 0;
sd = s;
for(int i=1; i+1<s.length(); i++){
if(sd[i]=='0' && sd[i-1]=='1' && sd[i+1]=='1' && ((i-2>=0 && sd[i-2]=='1') || (i+2<s.length() && sd[i+2]=='1'))){
one++;
sd[i] = '1';
}
}
for(int i=0; i<s.length(); i++){
if(sd[i]=='1' && i>1 && sd[i-1]=='1' && sd[i-2]=='1')continue;
else if(sd[i]=='1' && i>0 && sd[i-1]=='1')one++;
else if(sd[i]=='1')one++;
}

cout << min(zer, one) << "\n";
}