Stulen Sträng

면접 대비

시간 제한5초메모리 제한1024 MB

요약

문자열을 조각으로 나눠 두 사람에게 나누어 줄 때, 각자가 모든 문자를 같은 개수만큼 받도록 하는 최소 절단 횟수를 구한다.

난이도: 보통10점 중 6점
유형: 그리디, 누적 합, 문자열
정답자: 아직 제출이 없습니다

문제

Du och din kumpan Acsel har stulit en sträng av längd $n$ från er fiende Waxel. Ni vill nu dela upp strängen så att ni får exakt lika många av varje bokstav var. Det är dock dyrt att dela en sträng, därför är ditt uppdrag att hitta det minsta antalet delningar som krävs för att ni ska kunna dela lika på bytet.

Om till exempel strängen var "acabbc", så kan ni dela upp strängen i "a+cab+bc". Då kan du ta den första och sista biten medan Acsel tar mittenbiten. Här krävdes det två delningar, och det är också det minsta antalet i det här fallet.

입력

En rad med en sträng av längd $n$ , bestående av bokstäverna 'a', 'b', ... , 'a' $+(k-1)$ . För gränser på $n$ och $k$ , se nedan.

출력

Ett tal, det minsta antalet delningar som krävs. Om det inte är möjligt att dela exakt lika på bytet, skriv " $-1$ ".

예제3

예제 1
입력
```
abab
```
예상 출력
```
1
```
예제 2
입력
```
acabbc
```
예상 출력
```
2
```
예제 3
입력
```
abac
```
예상 출력
```
-1
```