A binary string is called *alternating* if no two adjacent characters of the string are equal. Formally, a binary string T of length M is called alternating if T_{i} \neq T_{i +1} for each 1 ≤ i < M. 

For example, 0, 1, 01, 10, 101, 010, 1010 are alternating strings while 11, 001, 1110 are not.

You are given a binary string S of length N. You would like to rearrange the characters of S such that the length of the longest alternating substring of S is maximum. Find this maximum value.

A binary string is a string that consists of characters 0 and 1. A string a is a [substring] of a string b if a can be obtained from b by deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.

------ Input Format ------ 

- The first line of input contains an integer T, denoting the number of test cases. The T test cases then follow:
- The first line of each test case contains an integer N.
- The second line of each test case contains the binary string S.

------ Output Format ------ 

For each test case, output the maximum possible length of the longest alternating substring of S after rearrangement.

------ Constraints ------ 

$1 ≤ T ≤ 10^{4}$
$1 ≤ N ≤ 10^{5}$
$S$ contains only the characters 0 and 1.
- Sum of $N$ over all test cases does not exceed $2 \cdot 10^{5}$.

----- Sample Input 1 ------ 
4
3
110
4
1010
4
0000
7
1101101

----- Sample Output 1 ------ 
3
4
1
5

----- explanation 1 ------ 
Test case $1$: Swapping the second and third characters makes $S=101$. Hence the length of the longest alternating substring is $3$ (choosing the entire string as a substring).

Test case $2$: The given string $S=1010$ is an alternating string of length $4$.

Test case $3$: The length of the longest alternating substring is $1$ for any rearrangement of  $S=0000$.

Test case $4$: One possible rearrangement of $S$ is $1\underline{10101}1$, which has an alternating substring of length $5$ (the substring starting at index $2$ and ending at index $6$).

Source: codechef | Difficulty: EASY
Tags: String algorithms

Data structures


Solutions:
for _ in range(int(input())):
	n = int(input())
	s = input()
	ones = s.count('1')
	zeros = n - ones
	pairs = 2 * min(ones, zeros)
	extra = min(abs(zeros - ones), 1)
	print(pairs + extra)


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	a = b = 0
	for i in s:
		if i == '1':
			a += 1
		else:
			b += 1
	if a == b:
		print(a + b)
	elif a + 1 == b or b + 1 == a:
		print(n)
	elif a == 0 or b == 0:
		print(1)
	else:
		print(2 * min(a, b) + 1)


for _ in range(int(input())):
	n = int(input())
	s = input()
	one = s.count('1')
	zero = n - one
	c = 0
	if one < zero:
		c = 2 * one + 1
	elif zero < one:
		c = 2 * zero + 1
	else:
		c = 2 * one
	print(c)


for i in range(int(input())):
	a = int(input())
	b = str(input())
	l = []
	l.append(b.count('0'))
	l.append(b.count('1'))
	s = min(l) * 2 + 1
	print(min(a, s))


for t in range(int(input())):
	n = int(input())
	s = input()
	o = s.count('1')
	z = n - o
	p = 2 * min(o, z)
	e = min(abs(z - o), 1)
	print(p + e)


for _ in range(int(input())):
	n = int(input())
	str = input()
	zeros = str.count('0')
	ones = str.count('1')
	if zeros == ones:
		print(2 * ones)
	elif zeros > ones:
		print(2 * ones + 1)
	else:
		print(2 * zeros + 1)


def fun(s, n):
	count0 = 0
	count1 = 0
	for i in s:
		if int(i) == 1:
			count1 = count1 + 1
		else:
			count0 = count0 + 1
	m = min(count0, count1)
	if count0 == n or count1 == n:
		return 1
	elif count0 == m and count1 == m:
		return count1 + count0
	else:
		return m + (m + 1)
for i in range(int(input())):
	n = int(input())
	s = input()
	print(fun(s, n))


n = int(input())
for i in range(n):
	s1 = int(input())
	s2 = input()
	if s2.count('0') == 0 or s2.count('1') == 0:
		print('1')
	elif s2.count('0') == s2.count('1'):
		print(2 * s2.count('0'))
	else:
		print(2 * min(s2.count('0'), s2.count('1')) + 1)


for _ in range(int(input())):
	n = int(input())
	b = input()
	if b.count('1') == b.count('0'):
		print(2 * b.count('1'))
	elif b.count('0') == 0 or b.count('1') == 0:
		print(1)
	else:
		print(2 * min(b.count('0'), b.count('1')) + 1)


for _ in range(int(input())):
	n = int(input())
	a = list(input())
	b = abs(a.count('1') - a.count('0'))
	if b <= 1:
		print(n)
	else:
		print(n - b + 1)


q = int(input())
for i in range(q):
	n = int(input())
	s = input()
	x1 = s.count('1')
	x0 = n - x1
	p = 2 * min(x1, x0)
	a = min(abs(x0 - x1), 1)
	print(p + a)


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	zero = 0
	one = 0
	for num in s:
		if num == '0':
			zero = zero + 1
		else:
			one = one + 1
	if zero == one:
		print(n)
	elif zero == 0 or one == 0:
		print(1)
	else:
		print(min(zero, one) * 2 + 1)


n = int(input())
for i in range(n):
	x = int(input())
	a = input()
	o = 0
	j = 0
	p = 0
	q = 0
	for i in a:
		if i == '0':
			p = 1
			o += 1
		else:
			q = 1
			j += 1
	if p == 0 or q == 0:
		print(1)
	elif j == o:
		print(j * 2)
	elif j > o:
		print(o * 2 + 1)
	else:
		print(j * 2 + 1)


for i in range(int(input())):
	N = int(input())
	S = input()
	a = S.count('0')
	b = S.count('1')
	if a == b:
		print(N)
	else:
		mins = min(a, b)
		print(2 * mins + 1 if mins != 0 else 1)


from collections import Counter
t = int(input())
for i in range(t):
	n = int(input())
	st = input()
	k = Counter(st)
	d = min(k['0'], k['1'])
	if k['1'] == k['0']:
		d = d * 2
	else:
		d = 1 + d * 2
	print(d)


for _ in range(int(input())):
	n = int(input())
	s = input()
	x = s.count('1')
	y = s.count('0')
	if x == y:
		print(n)
	elif x == 0 or y == 0:
		print(1)
	else:
		r = min(x, y)
		print(2 * r + 1)


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	z = s.count('0')
	y = s.count('1')
	pair = 2 * min(z, y)
	leftover = min(abs(z - y), 1)
	print(pair + leftover)


for t in range(int(input())):
	n = int(input())
	s = input()
	c_1 = s.count('1')
	c_2 = n - c_1
	pairs = 2 * min(c_1, c_2)
	extras = min(abs(c_1 - c_2), 1)
	print(pairs + extras)


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	a = s.count('0')
	b = s.count('1')
	pairs = 2 * min(a, b)
	extra = min(abs(a - b), 1)
	c = pairs + extra
	print(c)


for _ in range(int(input())):
	n = int(input())
	a = input()
	o = a.count('1')
	z = a.count('0')
	if o == 0 or z == 0:
		print(1)
	elif abs(o - z) == 0 or abs(o - z) == 1:
		print(o + z)
	else:
		print(min(o, z) + min(o, z) + 1)


for i in range(int(input())):
	h = int(input())
	x = input()
	y = x.count('0')
	z = x.count('1')
	if y == z:
		print(h)
	else:
		print(2 * min(y, z) + 1)
	y = 0


t = int(input())
for i in range(t):
	x = int(input())
	lst = list(map(int, input()))
	m = lst.count(0)
	n = lst.count(1)
	if m == n:
		print(x)
	else:
		print(2 * min(m, n) + 1)


for _ in range(int(input())):
	n = int(input())
	s = input()
	s0 = s.count('0')
	s1 = s.count('1')
	if s0 == s1:
		print(s0 + s1)
	else:
		print(min(s0, s1) * 2 + 1)


from itertools import permutations
for _ in range(int(input())):
	n = int(input())
	s = str(input())
	ones = s.count('1')
	zeros = n - ones
	pairs = 2 * min(ones, zeros)
	extra = min(abs(zeros - ones), 1)
	print(pairs + extra)


T = int(input())
for i in range(T):
	n = int(input())
	s = input()
	if s == s[0] * len(s):
		print(1)
	elif s.count('0') == s.count('1'):
		print(n)
	else:
		print(2 * min(s.count('0'), s.count('1')) + 1)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	if s.count('1') == s.count('0'):
		print(n)
	else:
		print(2 * min(s.count('1'), s.count('0')) + 1)


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	c = 0
	d = 0
	if n == 1:
		print('1')
	elif all((v == 0 for v in s)) or all((v == 1 for v in s)):
		print('1')
	else:
		for i in range(n):
			if s[i] == '0':
				c += 1
			else:
				d += 1
		if c == d:
			print(c + d)
		elif c < d:
			print(c + c + 1)
		elif d < c:
			print(d + d + 1)


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	freq = {}
	for j in s:
		if j in freq:
			freq[j] += 1
		else:
			freq[j] = 1
	one = 0
	zero = 0
	for key in freq:
		if key == '1':
			one += int(freq[key])
		else:
			zero += int(freq[key])
	if one == 0 or zero == 0:
		print(1)
	elif one == zero:
		print(2 * one)
	elif one > zero:
		print(2 * zero + 1)
	else:
		print(2 * one + 1)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	count1 = 0
	count0 = 0
	for i in s:
		if i == '1':
			count1 = count1 + 1
		elif i == '0':
			count0 = count0 + 1
	ans = min(count1, count0)
	if count1 > count0 or count0 > count1:
		print(ans + (ans + 1))
	elif count1 == count0:
		print(2 * ans)


for _ in range(int(input())):
	n = int(input())
	a = input()
	x = a.count('1')
	y = n - x
	p = 2 * min(x, y)
	q = min(abs(x - y), 1)
	print(p + q)


for i in range(int(input())):
	n = int(input())
	s = input()
	ans = [0, 0]
	for i in s:
		ans[int(i)] += 1
	x = min(ans)
	if x * 2 < n:
		print(x * 2 + 1)
	else:
		print(x * 2)


for i in range(int(input())):
	n = int(input())
	s = input()
	z = s.count('0')
	o = s.count('1')
	min1 = 2 * min(z, o)
	r = min(abs(z - o), 1)
	print(min1 + r)


for _ in range(int(input())):
	n = int(input())
	s = input()
	dic = {'0': 0, '1': 0}
	lis = [0] * n
	total = 0
	for i in s:
		if i == '1':
			dic['1'] += 1
		if i == '0':
			dic['0'] += 1
	if dic['0'] == n or dic['1'] == n:
		print(1)
	elif dic['0'] == dic['1']:
		print(n)
	else:
		if dic['0'] < dic['1']:
			total = dic['0'] + dic['0'] + 1
			print(total)
		if dic['1'] < dic['0']:
			total = dic['1'] + dic['1'] + 1
			print(total)


for i in range(int(input())):
	N = int(input())
	S = input()
	c = S.count('1')
	if N % 2 == 0:
		if abs(N - 2 * c) > 0:
			print(2 * min(c, N - c) + 1)
		else:
			print(2 * c)
	else:
		print(2 * min(c, N - c) + 1)


for i in range(int(input())):
	x = int(input())
	y = input()
	c0 = y.count('0')
	c1 = y.count('1')
	if c0 == c1:
		print(c0 * 2)
	else:
		print(min(c0, c1) * 2 + 1)


T = int(input())
for i in range(T):
	x = int(input())
	y = input()
	c0 = y.count('0')
	c1 = y.count('1')
	if c0 == c1:
		print(c0 * 2)
	elif c0 == 0 or c1 == 0:
		print('1')
	elif c0 > c1 or c1 > c0:
		print(min(c0, c1) * 2 + 1)


for i in range(int(input())):
	n = int(input())
	s = input()
	zc = 0
	oc = 0
	for j in range(n):
		if s[j] == '0':
			zc += 1
		else:
			oc += 1
	if zc == 0 or zc == n or oc == 0 or (oc == n):
		print('1')
	elif zc == oc:
		print(2 * zc)
	elif oc < zc:
		print(2 * oc + 1)
	else:
		print(2 * zc + 1)


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	s = input()
	l = [int(x) for x in s]
	st = set(l)
	if len(st) == 1:
		print(1)
		continue
	C = Counter(l)
	m1 = min(C.values())
	m2 = max(C.values())
	if m2 > m1 + 1:
		m2 = m1 + 1
	print(m1 + m2)


for i in range(int(input())):
	n = int(input())
	s = input()
	a = s.count('1')
	b = s.count('0')
	c = min(a, b)
	if a == b:
		print(len(s))
	else:
		d = c + (c + 1)
		print(d)


t = int(input())
while t:
	n = int(input())
	s = input()
	(ones, zeros) = (s.count('1'), s.count('0'))
	if any((i == 0 for i in [ones, zeros])):
		print(1)
	elif ones == zeros:
		print(n)
	else:
		print(min([ones, zeros]) * 2 + 1)
	t -= 1


t = int(input())
for tc in range(t):
	n = int(input())
	s = input()
	b = s.count('0')
	a = s.count('1')
	if abs(a - b) <= 1:
		print(n)
	elif a < b:
		print(2 * a + 1)
	elif b < a:
		print(2 * b + 1)


for i in range(int(input())):
	n = int(input())
	s = input()
	o = s.count('1')
	z = s.count('0')
	if abs(o - z) <= 1:
		print(n)
	elif o < z:
		print(o + o + 1)
	else:
		print(z + z + 1)


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	a = s.count('1')
	b = s.count('0')
	if abs(a - b) <= 1:
		print(len(s))
	elif a < b:
		print(a + a + 1)
	else:
		print(b + b + 1)


T = int(input())
for i in range(T):
	N = int(input())
	S = input()
	P = S.count('1')
	P1 = S.count('0')
	S1 = set(S)
	M = min(P, P1)
	if len(S1) == 1:
		print(1)
	elif len(S) % 2 == 0:
		if P == P1:
			print(P + P1)
		else:
			print(M * 2 + 1)
	else:
		print(2 * M + 1)


for _ in range(int(input())):
	x = int(input())
	y = str(input())
	l = []
	l.append(y.count('0'))
	l.append(y.count('1'))
	b = min(l) * 2 + 1
	print(min(x, b))


for _ in range(int(input())):
	x = int(input())
	s = input()
	s1 = s.count('1')
	z = len(s) - s1
	if z == s1:
		print(s1 * 2)
	else:
		print(min(s1, z) * 2 + 1)


test = int(input())
for i in range(test):
	x = int(input())
	s = input()
	y = s.count('1')
	z = len(s) - y
	if y == z:
		print(y * 2)
	else:
		print(min(y, z) * 2 + 1)


T = int(input())
for i in range(T):
	n = int(input())
	x = input()
	y = x.count('1')
	z = len(x) - y
	if y == z:
		print(y * 2)
	else:
		print(min(y, z) * 2 + 1)


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	n1 = 0
	n2 = 0
	for j in s:
		if int(j) == 0:
			n1 += 1
		else:
			n2 += 1
	if n1 > n2:
		print(n2 * 2 + 1)
	elif n1 < n2:
		print(n1 * 2 + 1)
	else:
		print(n1 * 2)


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	n0 = 0
	n1 = 0
	for i in s:
		if int(i) == 0:
			n0 = n0 + 1
		else:
			n1 = n1 + 1
	if n0 > n1:
		print(n1 * 2 + 1)
	elif n0 < n1:
		print(n0 * 2 + 1)
	else:
		print(n0 * 2)


for _ in range(int(input())):
	a = int(input())
	b = list(input())
	z = b.count('0')
	o = b.count('1')
	if z == o:
		print(z * 2)
	elif z < o:
		print(2 * z + 1)
	else:
		print(2 * o + 1)


t = int(input())
for i in range(t):
	n = int(input())
	s = list(input())
	z = s.count('0')
	o = s.count('1')
	if z == o:
		print(z * 2)
	elif z < o:
		print(2 * z + 1)
	else:
		print(2 * o + 1)


for t in range(int(input())):
	n = int(input())
	s = input()
	_0 = s.count('0')
	_1 = s.count('1')
	if _0 > _1:
		b = _0
		a = _1
	else:
		a = _0
		b = _1
	if a == 0 or b == 0:
		print(1)
	elif a == b or a == b - 1:
		print(n)
	else:
		print(2 * a + 1)


for _ in range(int(input())):
	lenstr = int(input())
	inpstr = list(map(str, input().split()))
	inpstr = inpstr[0]
	onecount = inpstr.count('1')
	zerocount = inpstr.count('0')
	if onecount == zerocount:
		print(lenstr)
	else:
		minvalue = min(onecount, zerocount)
		print(minvalue + minvalue + 1)


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	ones = s.count('1')
	zero = s.count('0')
	if ones == zero and n % 2 == 0:
		print(zero * 2)
	else:
		print(min(ones, zero) * 2 + 1)