Author: | Roman Bilyi |
Let's show that 2 operations are always enough:
Let be the minimum prefix length that has exactly same characters. Without loss of generality, it's character A. So there are characters A, b_p<n characters B and c_p<n characters C in prefix of length . Now we can replace segment [p+1, p+n-b_p] by B and segment [p+n-b_p+1, 3 \cdot n] by C. After that there are exactly characters A, B and C.
We should still check if it's possible to achieve the goal with 0 or 1 operation.
Zero operations are possible only if there are the same number of every character initially and we could check that.
Let's check if it's possible to use only one operation. Iterate over character which is used in this operation. Let this character be A. Let be the number of B and be the number of C in . We need to find such segment [l,r] that there are exactly characters B and characters C among S[1..l-1]+S[r+1..3n], where means concatenation of the strings. This means that there should be b-n characters B and c-n characters C in S[l..r]. Let's find values b_i and c_i — number of characters B and C respectively in prefix of length . Now segment [l, r] is good iff b_r-b_{l-1}=b-n and c_r-c_{l-1}=c-n. We can find if such segment exists using two pointers or set.
Complexity: .