PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: pd_codes
Tester: yash_daga
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
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.
EXPLANATION:
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 thats = 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.
TIME COMPLEXITY
\mathcal{O}(N) per test case.
CODE:
Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
u = input()
s = []
for c in u:
s.append(c)
if len(s) >= 3 and s[-1] == s[-2] == s[-3]:
s.pop()
s.pop()
print(*s, sep = '')