Contents

• # For Solution

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

• Flip: Pick an index ii (1i|S|)(1≤i≤|S|) and flip the ii-th character (i.e change 11 to 00 or 00 to 11). For e.g. 011001010001011_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–––––101001101001111_10→1001_10

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

## Flip or Compress solution codechef

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

### 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 SS equal.

## Flip or Compress solution codechef

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

## Flip or Compress solution codechef

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

## Flip or Compress solution codechef

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

• Original constraints

### Sample Input 1

3
100011
1110011
000101110


## Flip or Compress solution codechef

2
2
3


### Explanation

In the first test case,

• 1000––––11−→−−−−compress10111000_11→compress10_11
• 1011−→−flip111110_11→flip11_11

In the second test case,

• 1110011−→−flip11110111110_011→flip1111_011
• 1111011−→−flip111111111110_11→flip11111_11

## Flip or Compress solution codechef

In the third test case,

• 000101110−→−flip00011111000010_1110→flip00011_1110
• 00011111––––––0−→−−−−compress0001000011111_0→compress0001_0
• 00010−→−flip00000