Flip or Compress solution codechef

Flip or Compress solution codechef

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.

Input Format

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.

Constraints

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.

Subtasks

Flip or Compress solution codechef

Subtask #1 (5 points):

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

Subtask #2 (20 points):

Flip or Compress solution codechef

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

Subtask #3 (75 points):

  • Original constraints

Sample Input 1 

3
100011
1110011
000101110

Sample Output 1

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
  • For Solution

    Click Here!

 

  • Flip or Compress solution codechef

Leave a Comment