Problem: weak_typing_ch1 (2021 round1)

**Note: This problem shares similarities with Chapters [2](https://www.facebook.com/codingcompetitions/hacker-cup/2021/round-1/problems/A2/) and [3](https://www.facebook.com/codingcompetitions/hacker-cup/2021/round-1/problems/A3/). The solution to any chapter may help with solving the others, so please consider reading all of them first.**

Timmy the toddler is training to be a top typist. His teacher has assigned some homework in the form of a list of \(T\) string exercises to be typed, consisting of only the uppercase letters "F", "O", and "X".

Timmy is eating a popsicle on a hot summer afternoon, but still hopes to complete his homework. He would like to hold the popsicle with one hand, and type with the other. Unfortunately, Timmy is still a growing boy, and each of his hands is a tad too small to reach all the way across the keyboard. He can only reach the letters "F" and "X" with his left hand, and the letters "F" and "O" with his right.

Consider a string \(W\) which Timmy must type. Timmy may start typing with any hand of his choice (with the other holding the popsicle). He must then switch hands as necessary to type out the \(|W|\) letters in order, ending on any hand of his choice.

Given an exercise string \(W\) of length \(N\), let \(F(W)\) be the minimum number of times Timmy must switch hands to type \(W\). Please help Timmy compute the value of \(F(W)\).


# Constraints

\(1 \le T \le 80\)
\(1 \le N \le 800{,}000\)

Each string consists only of the letters "F", "O", and "X".
The sum of \(N\) across all exercises is at most \(4{,}000{,}000\).


# Input

Input begins with an integer \(T\), the number of exercises that Timmy has been assigned. For each exercise, there is first a line containing the single integer \(N\), followed by a second line containing the string \(W\) of length \(N\).


# Output

For the \(i\)th exercise, output a line containing *"Case #i: "* followed by a single integer, \(F(W)\).


# Sample Explanation

In the first exercise, if Timmy begins with his right hand, he can type the single letter "O" without needing to switch to his left hand.

In the second exercise, if Timmy begins with his left hand, he can type all \(3\) of the string's letters in order with \(1\) hand switch (for example, by switching to his right hand after typing the \(1\)st letter).

In the third exercise, Timmy can type the entire string with his right hand.

In the fourth exercise, it's possible for Timmy to type the string while only switching hands twice.


Sample input:
5
1
O
3
XFO
5
FFOFF
10
FXXFXFOOXF
13
XFOFXFOFXFOFX


Sample output:
Case #1: 0
Case #2: 1
Case #3: 0
Case #4: 2
Case #5: 6


Solution: The letter "F" may always be typed, whichever hand is being used. Therefore, occurrences of "F" in \(W\) have no bearing on which hand Timmy chooses to use, and may be ignored.

This leaves us with a reduced string \(W'\) of relevant letters, each being either "X" (only typeable with Timmy's left hand) or "O" (only typeable with his right hand). Whenever a "X" is followed by an "O" in \(W'\), Timmy must switch from his left hand to his right, and vice versa whenever an "O" is followed by a "X". Therefore, \(F(W)\) is equal to the number of pairs of consecutive differing letters in \(W'\).

[See David Harmeyer's solution video here](https://youtu.be/O1giTvqaxzM).


Code: #include <iostream>
using namespace std;

int N;
string W;

int solve() {
  cin >> N >> W;
  int p = -1, ans = 0;
  for (int i = 0; i < N; i++) {
    if (W[i] == 'F') {
      continue;
    }
    if (p >= 0 && W[i] != W[p]) {
      ans++;
    }
    p = i;
  }
  return ans;
}

int main() {
  int T;
  cin >> T;
  for (int t = 1; t <= T; t++) {
    cout << "Case #" << t << ": " << solve() << endl;
  }
  return 0;
}