PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: Kanhaiya Mohan
Tester: Abhinav Sharma, Aryan
Editorialist: Lavish Gupta
DIFFICULTY:
Easy-Medium
PREREQUISITES:
None
PROBLEM:
You are given a binary string A of length N. Rearrange the binary string to form binary strings S and T such that the length of the longest common substring between S and T is minimum.
Print both strings S and T.
Note that both S and T must be anagrams of A — see the examples below for more clarity.
EXPLANATION:
Let cnt_0 denotes the number of 0s in the string A, and let cnt_1 denotes the number of 1s. Without loss of generality, let us assume that cnt_0 \geq cnt_1.
Consider any string S. The $1$s in the string will be partitioning the string into cnt_1 + 1 blocks having non-negative number of 0s. By pigeonhole principle, at least one of the blocks will have \lceil \frac{cnt_0}{cnt_1 + 1} \rceil 0s. This means that the longest common substring will atleast have these many $0$s. This argument suggests us that we should have our S in such a way that $0$s are grouped as evenly as possible.
Examples
So, if A = 00000011, we should have S = 00100100. If we have A = 000000011, we should have S = 001001000. For now, let’s try to put extra 0s towards the end blocks. The reason will soon become clear.
After constructing S, we want to construct T so as to minimize the length of longest common substring. For this, we can greedily group all the 0s together, and all the 1s together. But should 0s come before 1s or vice-versa? Note that because of our construction of S, we have greater number of 0s towards end. A corner case arises when only the last partition contains larger number of 0s as compared to other partitions, as this partition is preceded by a 1 but is not followed by a 1. This suggests that we should first have 0s, and then 1s in T.
Examples
If A = 000000011, then we have S = 001001000.
Now, if T = 110000000, we have a common substring of length 4, as the last 1 of S is also getting matched. However, if we put T = 000000011, we will have a common substring of length 3 only, which is minimum as we discussed above.
TIME COMPLEXITY:
O(N) or O(N \cdot \log{N}) for each test case, depending on the implementation.
SOLUTION:
Editorialist’s Solution
Tester-1’s Solution
Tester-2’s Solution
Setter’s Solution