Problem A
Stulen Sträng

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 "$\textit{acabbc}$", så kan ni dela upp strängen i "$\textit{a}+\textit{cab}+\textit{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.

Indata

Den första och enda raden består innehåller 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.

Utdata

Skriv ut ett heltal, det minsta antalet delningar som krävs. Om det inte är möjligt att dela exakt lika på bytet, skriv ut “$-1$”.

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

abab

1

acabbc

2

abac

-1