Bob and Alphabet
Tag(s):

## Algorithms, Dynamic Programming, Medium

Problem
Editorial
Analytics

Bob has arranged $N$ boxes in a straight line. Each box has a Latin Character $('a' - 'z')$ written on it. He wants to chain $26$ boxes in such a way that the chain starts from box with alphabet $'a'$ and contains all Latin Characters exactly once in increasing lexicographic order, ending at $'z'$. In other words, the chain must form the following sequence:
$'abcdefghijklmnopqrstuvwxyz'$

To join a box $b_i$ and $b_j$ with chain, the length of the chain to be used is $|i - j|$.
Help Bob to minimize the total length of the chain used to make the desired sequence.

Input Format:
First line of input contains of a single integer $T$ - the number of testcases.
Each testcase consists of a single line, which contains a string made up of lowercase Latin Characters - $'a'$ to $'z'$. The string may have one or more occurrences of each character.

Output Format:
For each testcase, print a single integer - the minimum length of chain required to make the required sequence.

Input Constraints:
$1 \le T \le 10$
$26 \le |S| \le 10^6$
All 26 characters ('a' - 'z') are present in $S$ at least once.

SAMPLE INPUT
2
abcdefghijklmnopqrstuvwxyz
ceaabcdefghijklmnopqrstuvwxyz

SAMPLE OUTPUT
25
25

Explanation

Testcase 1:
There is only one way to connect the chain for this sequence. The chain starts from $S_0$, then connects to $S_1$, then $S_2$, ... , $S_{25}$, which creates the sequence $'abcdefghijklmnopqrstuvwxyz'$. Hence, the answer for testcase 1 is $25$ as the total length of the chain used is:
$(b_0 -> b_1) + (b_1 -> b_2) + ... + (b_{24} -> b_{25}) = |0 - 1| + |1 - 2| + ... + |24 - 25| = 1 + 1 + ... + 1 = 25.$

Testcase 2:
There are several chain sequences that can possibly be made from the given sequence.
A few of them are:
1. $S_2 -> S_4 -> S_0 -> S_6 -> S_7 -> S_8 -> ... -> S_{25}$
2. $S_3 -> S_4 -> S_5 -> S_6 -> ... -> S_{25}$
Among the possible chain sequences, the sequence 2. listed above provides the minimum length of chain used.

Time Limit: 3.0 sec(s) for each input file.
Memory Limit: 512 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

Via.com Java Hiring Challenge

OTHER PROBLEMS OF THIS CHALLENGE
• Math > Number Theory