C - Alternated Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 350 点

問題文

長さ 2N の文字列 S が与えられます。 S は A, B を N 個ずつ含みます。

S に対して隣り合う文字を入れ替える操作を好きな回数( 0 回でもよい)行って、同じ文字が隣り合う箇所がない状態にするために必要な操作回数の最小値を求めてください。

制約

  • 1\leq N \leq 5\times 10^5
  • N は整数
  • S は長さ 2N の文字列であり、N 個の A と N 個の B からなる

入力

入力は以下の形式で標準入力から与えられる。

N
S

出力

答えを出力せよ。

入力例 1

3
AABBBA

出力例 1

2

次のように操作することで 2 回の操作で同じ文字が隣り合う箇所がない状態にすることができます。

  • 2 文字目と 3 文字目を入れ替える。S は ABABBA になる。
  • 5 文字目と 6 文字目を入れ替える。S は ABABAB になる。

入力例 2

3
AAABBB

出力例 2

3

入れ替えることができるのは隣り合う文字に限ることに注意してください。

入力例 3

17
AAABABABBBABABBABABABABBAAABABABBA

出力例 3

15

Score : 350 points

Problem Statement

You are given a string S of length 2N. S contains exactly N occurrences of A and N occurrences of B.

Find the minimum number of operations (possibly zero) needed to make S have no adjacent identical characters, where an operation consists of swapping two adjacent characters in S.

Constraints

  • 1\leq N \leq 5\times 10^5
  • N is an integer.
  • S is a string of length 2N consisting of N occurrences of A and N occurrences of B.

Input

The input is given from Standard Input in the following format:

N
S

Output

Print the answer.

Sample Input 1

3
AABBBA

Sample Output 1

2

By performing operations as follows, you can achieve a state with no adjacent identical characters in two operations:

  • Swap the 2nd and 3rd characters. S becomes ABABBA.
  • Swap the 5th and 6th characters. S becomes ABABAB.

Sample Input 2

3
AAABBB

Sample Output 2

3

Note that you can only swap adjacent characters.

Sample Input 3

17
AAABABABBBABABBABABABABBAAABABABBA

Sample Output 3

15