ALTSTR Editorial


Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Soumyadeep Pal
Tester: Aryan, Takuki Kurokawa
Editorialist: Pratiyush Mishra






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.


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)


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


Editorialist’s Solution
Setter’s Solution
Tester-1’s Solution
Tester-2’s Solution

1 Like