Arranging Books

Interview

Time limit1sMemory limit1024 MB

Summary

Given a string of L, M, and S characters, find the minimum number of swaps of two characters needed so that all L come first, then all M, then all S.

Level: Medium5 of 10
Topics: Greedy, String, Array, Math
Solved: No attempts yet

Problem

Valentina wants the books on a shelf to be arranged in a particular way. Every time she sees a shelf of books, she rearranges them so that all the large books appear on the left, followed by all the medium-sized books, and then all the small books on the right. She does this by repeatedly choosing any two books and exchanging their locations. Exchanging the locations of two books is called a swap.

Help Valentina determine the fewest number of swaps needed to arrange a shelf of books as she wishes.

Input

The input consists of exactly one line containing at most 500 000 characters. Each character is L, M, or S.

Output

Output a single integer equal to the minimum possible number of swaps needed to arrange the books so that all occurrences of L come first, followed by all occurrences of M, and then all occurrences of S.

Examples2

Example 1
Input
```
LMMMS
```
Expected output
```
0
```
Example 2
Input
```
LLSLM
```
Expected output
```
2
```