Same Parity Swaps in Binary Strings Codechef Solution

by

Same Parity Swaps in Binary Strings Codechef Solution

You are given a binary string S of length N (i.e. every character of S is either 0 or 1).

You can perform the following operation on S:

select any two indices i,j of the same parity, i.e. either both i,j are odd or both i,j are even
swap Si and Sj For example, in the string 1110, we can swap the second and the fourth characters to get 1011. However, we can never obtain 1101 from 1110 by performing such swaps.

Find the maximum possible number of occurrences of the string 01 as a substring of S after performing the above operation any number of times (it is also allowed to not perform any operation).

For example, the string 1110 has no occurrence of the string 01 as a substring, whereas we can swap the second and fourth characters to obtain 1011 which has exactly one occurrence of 01 (colored red).

Input Format

  • The first line of input contains an integer T, denoting the number of testcases. The description of the T testcases follow.
  • Each testcase consists of two lines.
  • The first line contains a single integer N, the length of the string S.
  • The second line contains a binary string of length N.

Output Format
For each testcase, print in a single line, an integer — the answer as per the problem statement.

Constraints

  • 1≤T≤4000
  • 1≤|S|≤105
  • The sum of |S| over all testcases doesn’t exceed 105

Subtasks
Subtask #1 (100 points): Original constraints

Sample Input 1
3
5
00100
5
01010
5
10001

Sample Output 1
1
2
2

Explanation

  • Test case 1: The only strings that can be obtained by performing the given operations are {10000,00100,00001}. Of these the two strings 00100 and 00001 contain exactly one occurrence of 01.
  • Test case 2: The given string S cannot be changed by performing the given operation and contains 2 occurrences of the string 01, i.e. 01010.
  • Test case 3: The only strings that can be obtained by performing the given operations are {00101,10001,10100}. The string 00101 contains two occurrences of 01.

SOLUTION

Program: Same Parity Swaps in Binary Strings Codechef Solution in Python

T = int(input())
for i in range(T):
    N = int(input())
    S = input()
    a = S.count('1')
    b = S.count('0')
    x = ''
    S1 = ''
    for j in range(1, N + 1):
        if j % 2 == 0:
            x = '1'
        else:
            x = '0'
        S1 += x
    if S == S1:
        print(S.count("01"))
    elif a < b:
        print(a)
    elif b < a:
        print(b)
    else:
        print(a - 1)

Program: Same Parity Swaps in Binary Strings Codechef Solution in C++

#include<iostream>
using namespace std;
int main(){
   int t;
   cin>>t;
   while(t--){
       int n,a=0,b=0;
       bool z=false;
       string s;
       cin>>n;
       cin>>s;
       for(int i=0;i<n;i++){
           if(s[i]==s[i+1]){
             z=true;
           }
           if(s[i]=='0'){
             a++;  
           }
           else
           b++;
       }
       if(a<b){
           cout<<a<<endl;
       }
       else if(b<a){
           cout<<b<<endl;
       }
       else if(a==b && z==true){
           cout<<a-1<<endl;
       }
       else if(a==b && s[0]=='1'){
           cout<<a-1<<endl;
       }
       else
       cout<<a<<endl;
   }
}

Program: Same Parity Swaps in Binary Strings Codechef Solution in Java

import java.util.*;
import java.lang.*;
import java.io.*;
class Codechef
{
	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
		Scanner  sc=new Scanner(System.in);
		
		int t=sc.nextInt();
		
		while(t-->0){
		    
		    int n=sc.nextInt();
		    String s=sc.next();
		    
		    char ch[]=s.toCharArray();
		    // System.out.println(c);
		    
		    int a=0,b=0,c=0,d=0;
		    int i=0;
		    for(char c1:ch){
		        
		        if(c1=='1'){
		            if(i%2==1)a++;
		            else b++;
		        }
		        else{
		            if(i%2==1)c++;
		            else d++;
		                
		        }
		        i++;
		    }
		    int count=Math.min(a,d);
		    
		    if(a==d){
		        
		        if(b>0){
		            b--;
		          count+=  Math.min(b,c);
		        }
		    }
		   else if(d==count){
		       
		       b--;
		       count+=Math.min(b,c);
		    }
		    else{
		        
		        count+=Math.min(b,c);
		    }
		  
		  
		   System.out.println(count);
		    
		    
		}
		
	}
}

Related:

Leave a Comment

4 − 4 =