PROBLEM LINK:
Editorialist: Soumik Sarkar
DIFFICULTY:
EASY
PREREQUISITES:
Basic string manipulation
PROBLEM:
Given a circular chain S that contains stones of two types only, Ruby and Amber, minimize the length of the longest contiguous sequence of stones of the same type, defined as the beauty factor B, after replacing exactly one stone with its complementary type.
EXPLANATION:
Be prepared, this problem is all about corner cases. But first let’s do some basic processing of the string.
Let the length of S be N. We need to break S into segments such that each segment contains only one type of stone and is as long as possible. We can do that in linear time using something like this
A = empty list
i = 0
while i < N:
j = i + 1
while j < N and S[j] == S[i]:
j = j + 1
L = j - i
append L to back of A
i = j
Now A will contain the length of each segment. For example, if S = “AARRRARRAA”, we will obtain A as [2, 3, 1, 2, 2].
But, because the chain is circular, the first and last segments can be combined into a larger segment if they are of the same stone type and if there are more than 1 segments to begin with. So we must do
if length(A) > 1 and S[0] == S[N-1]:
A[0] = A[0] + A[length(A)-1]
delete the last element from A
So from the previous example, A would be changed to [4, 3, 1, 2].
General case
Let’s consider the general case. Our aim is to minimize the beauty factor B which is the length of the longest segment. So we would want to choose the current longest segment in S, and replace the stone at its center, which would split it into 3 separate segments. If the length of the current longest segment is B, The left and right ones would be of size \left\lfloor\frac{B}{2}\right\rfloor and \left\lfloor\frac{B}{2}\right\rfloor or \left\lfloor\frac{B}{2}\right\rfloor - 1 depending on whether m is odd or even. The middle segment would be just a single stone with length 1. Hence the longest segment which replaced B is \left\lfloor\frac{B}{2}\right\rfloor.
So after replacement, the new longest segment would either be the second longest segment from before, let it be B_1, or the newly created segment \left\lfloor\frac{B}{2}\right\rfloor.
Corner cases
Case 1: There is only 1 segment
Because the chain is circular, splitting the only segment at the middle is just the same as splitting it anywhere else, and it only decreases the length of the segment by 1. New beauty is B-1. Example: “RRRRRRRRR” → "RRRRRARRR"
Except when the size of segment is 1, and replacing the single stone has no effect on the current beauty factor 1. Example: “A” → "R"
Case 2: B is 1
If there are exactly 2 segments of length 1, we must replace any one of those which will make it match the other, so beauty will change to 2. Example: “AR” → "RR"
If there are more than 2 segments, replacing any stone will make it match both its neighbours, so beauty will be 3. Example: “RARARA” → "RARRRA"
Case 3: B is 2
If all segments have length 2, replacing any one stone will make it match with the neighbour segment, so new beauty will be 3. Example: “AARRAARR” → "AARRAAAR"
But if there is any segment of length 1, we can replace the stone next to that so that the beauty remains 2. Example: “RRARRAA” → "RRAARAA"
That covers all the cases. The complexity is \mathcal{O}(N).
EDITORIALIST’S SOLUTION:
Editorialist’s solution can be found here.