문제1441--Minimum Swap

1441: Minimum Swap

실행시간 제한: 1 Sec  메모리사용 제한: 128 MB
제출: 151  통과: 45
[제출] [채점기록] [묻고답하기]

문제 설명

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 \leq | S | \leq 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.

 

입력 예시 Copy

abc
cba
acb
bdca
fedcba

출력 예시 Copy

0
1
1
2
3

출처/분류