Help me in solving BIS problem

help
,
1

My issue

breaking the array in 2 halves and counting no. of 0’s in first half and adding length of 2nd half to it

My code

for _ in range(int(input())):
    p = int(input())
    s = input()
    l = []
    for i in range(0,len(s)):
        l.append(int(s[i]))
    m = []
    n = []
    for i in range(0,len(s)//2):
        m.append(l[i])
    for j in range(len(s)//2,len(s)):
        n.append(l[j])
    c = 0
    if 1 not in n:
        print(len(s))
    else:
        for i in m:
            if i==0:
                c=c+1
        print(c+p)

Problem Link: Binary Substring Practice Coding Problem - CodeChef

2

Breaking the string doesn’t actually help you at all.

You are asked to perform any amount of times the so-called operation:

image

This basically implies swapping pairs of bits like this:

0110 → 1001

So a useful approach was to handle them as pairs, and count how many we have of each available to swap.

  • It’s intuitive to think that a pair of “00” or “11” makes a substring of at least 2. When joinned, then an ever larger.
  • A “01” (if exists) can be put in between of the “00” and “11”
  • If you have 1 “10”, you can put it at the begging or at the end. If you have 2, one in the beggining, and one in the end.

This was a way to use them:

  • 10 00 01 11 10

And you get a length 8 non-decreasing substring.

If you have more “01” or “10”, you can NOT add them. But you could add more “00” or “11”.

for T in range(int(input()):
    
    N = int(input())
    S = input()
    
    _00 = 0
    _01 = 0
    _10 = 0
    _11 = 0
    
    for i in range(0,N,2):
        _00 += int(S[i] == '0' and S[i+1] == '0') 
        _01 += int(S[i] == '0' and S[i+1] == '1') 
        _10 += int(S[i] == '1' and S[i+1] == '0') 
        _11 += int(S[i] == '1' and S[i+1] == '1') 
    
    print(min(_10,2) + 2*(_00+_11) + 2*int(_01>0))