GIven a string of length n. where the first k elements are “R” and the next n-k elements are “B”. we have to print Alice wins if(k>n-k) else print Bob wins
This is a classic binary search problem. The idea is to find the value of k using a modified binary search.
pseudo code of modified binary search binary search
while(s[first]=="R" and s[last]=="B"): mid=(first+last)//2 if(s[mid]=="R"): f=mid+1 elif(s[mid]=="B"): l=mid-1 if(s[first]=="B"): nr=first nb=n-first elif(s[last]=="R"): nr=last+1 nb=n-nr
Initially first=0 and last=n-1 and mid=(first+last)/2. Here logic is to find value of mid such that s[mid] is R and s[mid+1] =B or s[mid] is B and s[mid-1] is R.In the first case k=mid+1 and in the second case k=mid.now we have to just compare k and n-k.if k is greater than n-k then Alice wins else Bob wins .
for _ in range(int(input())): n=int(input()) s=input() f=0 l=n-1 while(s[f]=="R" and s[l]=="B"): mid=(f+l)//2 if(s[mid]=="R"): f=mid+1 elif(s[mid]=="B"): l=mid-1 if(s[f]=="B"): nr=f nb=n-f elif(s[l]=="R"): nr=l+1 nb=n-nr if(nr>nb): print("Alice wins") else: print("Bob wins")