# PROBLEM LINK:

Contest Division 1

Contest Division 2

Contest Division 3

Contest Division 4

Setter: Soumyadeep Pal

Tester: Aryan, Takuki Kurokawa

Editorialist: Pratiyush Mishra

# DIFFICULTY:

Cakewalk/Simple

# PREREQUISITES:

None

# PROBLEM:

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 Ti≠Ti+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.

# EXPLANATION:

To form the given string of maximum length, we calculate the number of 1’s and 0’s in the original string.

Let n_1, n_0 be the counts respectively.

**Case1: n_0 = n_1**

(Keeping either ‘0’ or ‘1’ in the beginning and alternating)

\implies ans = 2*n_1

**Case2: n_0 < n_1**

(Keeping ‘1’ in the beginning and alternating)

\implies ans = 2*n_0+1

**Case3: n_0 > n_1**

(Keeping ‘0’ in the beginning and alternating)

\implies ans = 2*n_1+1

The above three cases can be mathematically combined in a single equation as:

ans = 2*min(n_0,n_1) + (n_1!=n_0)

# TIME COMPLEXITY:

The above calculation can be done in constant time. However, calculating n_1 and n_0 requires a complete iteration of the string. Hence, the solution has a time complexity of O(N).

# SOLUTION:

Editorialist’s Solution

Setter’s Solution

Tester-1’s Solution

Tester-2’s Solution