Minimizing Flips for Two-Segment Coin Configuration

You are given an integer \(n\) and a string of length \(n\) composed of characters 'H' (heads) and 'T' (tails). Each coin represents its state, and we define a segment as a maximal contiguous subsequence of identical coins. Your task is to compute the minimum number of coin flips required so that the entire sequence is arranged in at most two segments. A coin flip changes an 'H' to a 'T' or vice versa.

More formally, if the number of segments in the given coin sequence is \(s\), then the number of flips required is \(\left\lfloor \frac{s-1}{2} \right\rfloor\). The goal is to achieve a configuration with no more than two segments.

Example: For the coin sequence "HHTTHT" of length 6, there are 4 segments: "HH", "TT", "H", "T". Thus, the minimum number of flips required is \(\left\lfloor \frac{4-1}{2} \right\rfloor = 1\).

inputFormat

The input is read from stdin and contains two lines:

• The first line contains an integer \(n\), the number of coins.
• The second line contains a string of length \(n\) representing the initial state of the coins using the characters 'H' and 'T'.

outputFormat

Output to stdout a single integer representing the minimum number of flips required to arrange the coins into at most two segments.

6
HHTTHT

1