PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: Jeevan Jyot Singh
Testers: Tejas Pandey, Hriday
Editorialist: Nishank Suresh
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
Given a binary string S, in one move you can insert either 0 or 1 at any position. Find the minimum number of moves so that the resulting string has no adjacent equal characters.
EXPLANATION:
Note that a single move allows us to ‘break apart’ exactly one pair of equal adjacent characters, by inserting either 1 between 00 or 0 between 11.
Further, this move doesn’t create any new equal adjacencies.
So, the answer is simply the number of pairs that are already adjacent and equal, i.e, positions i \ (1 \leq i \lt N) such that S_i = S_{i+1}, which can be computed with a simple for loop.
TIME COMPLEXITY
\mathcal{O}(N) per test case.
CODE:
Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
s = input()
print(sum(1 if s[i] == s[i+1] else 0 for i in range(n-1)))