PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
Given a string S, find the minimum number of changes needed to ensure that there doesn’t exist any index i with S_i = S_{i+1} = S_{i+2}.
EXPLANATION:
A natural greedy solution is as follows: process the string from left to right, and if the current character is equal to the previous two characters, change the current character.
That is, for each i = 1, 2, \ldots, N in order,
- If S_i = S_{i-1} = S_{i-2}, then change the character at index i to something else.
- Otherwise, don’t change it.
This greedy is indeed correct.
To see why: let i be the smallest index such that S_i = S_{i-1} = S_{i-2} in the original string.
Certainly, we must change at least one of these three characters.
Of them, it’s most beneficial to change S_i itself; because doing this will allow us to “fix” more triplets too: in particular the triplets (S_{i-1}, S_i, S_{i+1}) and (S_i, S_{i+1}, S_{i+2}) can be fixed by changing S_i; in case they were previously all-equal.
Since we’re allowed to change to any character we like, it’s always possible to find a valid choice to change S_i to that doesn’t affect future triplets.
For example, just change S_i to any character that’s neither S_{i-1} nor S_{i+1}, and automatically no conflicts are created.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n = int(input())
s = input()
ans = 0
i = 2
while i < n:
if s[i] == s[i-1] and s[i] == s[i-2]:
ans += 1
i += 3
else:
i += 1
print(ans)