You are given a string s. You need to reform the string in such a way that there exists at least one substring of length 26 which contains all the lowercase English alphabets. The order of the characters does not matter.
To reform the substring, you are allowed to do some swap operations. In one swap operation, you can choose any two positions i and j (1 ≤ i ≤ j ≤ |s|) and swap the characters at those positions.
Now you need to calculate the minimum number of swap operations required to reform the given string.
Input
The only line of the input contains a string s.
Constraints:
26 ≤ |s| ≤ 100000
All the characters will be lower case English alphabets.
Output
Print the minimum number of swap operations required. If a valid reformation is not possible then print -1.
Samples
| Input | Output |
|---|---|
opqraacdefghijklmnbbstuvwxyz | 2 |
| Input | Output |
|---|---|
tubttdasfxyalmnopazacbdefghijkqrs | -1 |
Explanation:
Case 1: Swapping pair (1, 5) and (20, 28) will form a substring (2, 27) which contains all the lowercase English alphabets.
Case 2: Alphabet 'w' and 'v' are missing in the given string. So a valid reformation is not possible.
