頁面無法載入？點擊這裡可能會修復。
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

需要登入才能撰寫程式碼。