Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Reform A Substring

By Kimbbakar · Limits 2s, 512 MB

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

InputOutput
opqraacdefghijklmnbbstuvwxyz
2
InputOutput
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.

Discussion

Statistics


85% Solution Ratio

allllekssssaEarliest, Jul '18

lliimmFastest, 0.0s

NirjhorLightest, 262 kB

nafi32Shortest, 629B

Submit

Login to submit

Toph uses cookies. By continuing you agree to our Cookie Policy.