회문
면접 대비시간 제한1초메모리 제한1024 MB
a와 b로 이루어진 문자열을 인접한 두 문자의 교환으로 팰린드롬으로 만드는 최소 횟수를 구합니다. 불가능하면 -1을 출력합니다.
문제
Bajtek은 정보 동아리에서 회문(palindrom)이 무엇인지 배웠다. 회문은 왼쪽에서 오른쪽으로 읽어도, 오른쪽에서 왼쪽으로 읽어도 같은 단어다. 예를 들어 oko, kajak, kobyłamamałybok, ababbaba는 회문이고, kajaki, zoo, alamakota, abaababa는 회문이 아니다.
새로 배운 지식이 반가웠던 Bajtek은 메모장을 열고 a와 b 글자로만 이루어진 단어를 적었다. 잠시 후 그 단어가 회문일 필요는 없다는 것을 깨달았다. 그는 단어를 고치기로 했다. 1초에 인접한 두 글자를 골라 자리를 바꿀 수 있다. 이런 이동을 여러 번 하거나 아무것도 하지 않아서 단어를 회문으로 만들 수 있을까? 가능하다면 이 변경에 드는 최소 초는 얼마인가? 이를 계산하는 프로그램을 작성하라.
입력
한 줄에 Bajtek의 메모장에 적힌 비어 있지 않은 단어가 주어진다. 단어는 a와 b 문자만 포함하며, 길이는 200,000을 넘지 않는다.
출력
Bajtek의 단어를 회문으로 바꾸는 데 필요한 최소 초를 정수 하나로 출력한다. 불가능하면 -1을 출력한다.
힌트
첫 번째 예제에서 Bajtek은 예를 들어 abbaaab → babaaab → baabaab 순서로 바꿀 수 있고, 이는 2초 만에 단어를 회문으로 만든다. 이보다 빠른 방법은 없음을 보일 수 있다.
두 번째 예제에서 단어는 ab 또는 ba다. 둘 다 회문이 아니므로 Bajtek은 과제를 수행할 수 없다.