Official Analysis (C++, Java, and Python)

Explanation

We want to maximize the number of Guernseys in even positions. Looking at pairs of adjacent cows, HH contributes nothing, GG always contributes one, and GH/HG can contribute one depending on its orientation. We only consider adjacent pairs with the first cow being in an odd position to avoid overlapping. We say a mixed GH/HG pair is aligned if it is HG and misaligned if it is GH.

Since reversing a prefix flips the orientation of all earlier pairs, we can iterate through pairs from right to left, keeping track of whether our flips have switched the orientation or not.

If a mixed pair is already aligned under the current orientation, we leave it. Otherwise, we must flip it. A pair is misaligned exactly when its Guernsey ends up on an odd position under the current parity of flips. Each flip is both necessary and sufficient, so the number of times we need to flip misaligned pairs is exactly the minimum number of reversals needed.

Implementation

Time Complexity: $\mathcal{O}(N)$

Copy
#include <cassert>
#include <iostream>
#include <string>

using std::cout;
using std::endl;
using std::string;

int main() {
	int cow_num;

Copy
import java.io.*;

public class Photoshoot {
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
		int cowNum = Integer.parseInt(read.readLine());
		String cows = read.readLine();
		assert cows.length() == cowNum && cowNum % 2 == 0;
		read.close();

Copy
cow_num = int(input())
cows = input()
assert len(cows) == cow_num and cow_num % 2 == 0

flips = 0
for c in range(cow_num - 2, -1, -2):
	sub = cows[c : c + 2]
	if sub[0] == sub[1]:
		continue
	if (sub == "GH" and flips % 2 == 0) or (sub == "HG" and flips % 2 == 1):
		flips += 1

print(flips)