CONSTR - Editorial


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

Author: pd_codes
Tester: yash_daga
Editorialist: iceknight1093






On a string S, you can perform the following operation:

  • Choose an index 1 \leq i \leq |S|, and replace S_i with three occurrences of S_i

You’re given a string U, find a string S such that it can be converted into U using the maximum number of moves possible.


In this problem, it helps to look at the process in reverse.
That is, instead of replacing a character with three of its occurrences, we take three consecutive occurrences of a character and replace it with a single one.

For example, the string \texttt{aaaabccc} can be turned into \texttt{aabccc} or \texttt{aaaabc} in one move this way.

So, we can start from U and then perform this reverse move as many times as possible to obtain the string S we’re looking for.

To do this, observe that we can simply greedily delete characters.
That is, as long as there are three equal adjacent characters, delete two of them.

Directly deleting from a string can be slow, so you’ll need to be a bit clever with implementation.
One way to implement this is as follows:

  • Let S be the answer string, initially empty.
  • Iterate i from 1 to N.
  • Append U_i to S, by doing s += u[i] (note that s = s + u[i] is a linear operation and will lead to TLE in this problem)
  • If the last three characters of S are now equal, delete two of them. Since we’re deleting from the end, this can be done in \mathcal{O}(1) time.

Finally, print the string S.


\mathcal{O}(N) per test case.


Editorialist's code (Python)
for _ in range(int(input())):
    n = int(input())
    u = input()
    s = []
    for c in u:
        if len(s) >= 3 and s[-1] == s[-2] == s[-3]:
    print(*s, sep = '')
1 Like

i did operation directly on the string, checked that if 3 characters are equal continuously then deleted two of them and shifted the index back to zero.
check my solution and please explain what is am i doing WRONG.

Your should set i = -1, not i = 0 (because the for loop will increment i in the next step).

1 Like

Thankyou brother, very very thanks.