Bob and Alphabet

0

0 votes
Dynamic Programming, Recruit, Medium, Algorithms, Ready, Approved
Problem

Bob has arranged N boxes in a straight line. Each box has a Latin Character (az) 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 bi and bj with chain, the length of the chain to be used is |ij|.
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:
1T10
26|S|106
All 26 characters ('a' - 'z') are present in S at least once.

Time Limit: 3
Memory Limit: 512
Source Limit:
Explanation

Testcase 1:
There is only one way to connect the chain for this sequence. The chain starts from S0, then connects to S1, then S2, ... , S25, which creates the sequence abcdefghijklmnopqrstuvwxyz. Hence, the answer for testcase 1 is 25 as the total length of the chain used is:
(b0>b1)+(b1>b2)+...+(b24>b25)=|01|+|12|+...+|2425|=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. S2>S4>S0>S6>S7>S8>...>S25
2. S3>S4>S5>S6>...>S25
Among the possible chain sequences, the sequence 2. listed above provides the minimum length of chain used.

Editor Image

?