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