页面无法加载？点击这里可能会修复。
Placeholder

#7038

중복문자열 1s 1024MB

问题

중복문자열이란, 길이가 짝수이며 앞쪽 절반의 부분문자열이 뒤쪽 절반의 부분문자열과 같은 문자열을 일컫는다.

예를 들어, abcabc는 중복문자열이지만 ababab는 중복문자열이 아니다.

길이 2N의 문자열에서 인접한 위치의 문자를 교환하는 연산을 적절히 시행하여 전체 문자열이 중복문자열이 되도록 하고 싶다.

인접한 위치의 문자를 교환하는 연산의 최소 시행 횟수를 구하시오.


输入

첫 줄에 N이 주어진다. (1<=N<=100000)

그 다음 줄에 길이 2N의 영어 소문자로 구성된 문자열이 주어진다.

단, 이 문자열은 항상 중복문자열이 되도록 할 수 있다.


输出

중복문자열이 되게 하는 연산의 최소 횟수를 한 줄에 출력하시오.


子任务

编号 分数 条件
#110分

문자열에 'a'가 N개, 'b'가 N개 주어진다.

#220分

각 문자는 최대 2번 등장한다.

#320分

앞쪽 절반의 문자의 집합과 뒤쪽 절반의 문자의 집합이 같다. (중복 고려)

#420分

N<=1000

#530分

제한 없음


示例 #1

3
koeeok
3

示例 #2

3
kekoeo
1

示例 #3

4
soolnlsn
4

soolnlsn -> solonlsn -> solnolsn -> oslnolsn -> olsnolsn



来源

COCI 2021/2022 Contest #3

需要登录才能编写代码。