All Tracks Problem
SOLVE
LATER
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.
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.
CODE EDITOR
Contributor
This Problem was Asked in
-
-
Math > Number Theory
