# ALTSTR Editorial

Tester: Aryan, Takuki Kurokawa
Editorialist: Pratiyush Mishra

Cakewalk/Simple

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).

1 Like