ACM/ICPC Indonesia National Contest 2007
Time Limit: 1s
Sorting a sequence either into ascending or descending order is a common problem in real world.
One of the most common methods in sorting algorithm is comparing and swapping any two elements in the sequence. Supposed I have invented a new sorting algorithm which uses this swapping method. I need to compare the number of swaps occurred in my algorithm with the minimum number of swaps that actually needed to sort some sequences.
Help me determine the minimum number of swaps needed to transform a sequence of characters into a sorted sequence in ascending order. In this problem, you may assume that each character will appear at most once in the sequence.
Each line contains a sequence of lowercase characters S (1 <= | S | <= 26). There will be no repeated characters in S and each ith character (0 < i < | S |) is in range ['a'...'z']. Input is terminated by EOF.
For each test case, output a line containing the minimum number of swaps to transform it into a sorted sequence of characters in ascending order.
Problem Setter: Lego Haryanto