Minimum Swaps to Sort a String

You are given a string s consisting of lowercase Latin letters. Your task is to determine the minimum number of swaps required to sort the string into alphabetical order.

The swaps considered here are based on the idea of counting inversions: an inversion is a pair of indices i and j such that i < j and s[i] > s[j]. The total number of inversions in the string is equal to the minimum number of adjacent swaps needed to sort the string.

Note: Although the computation of inversions typically corresponds to the number of swaps required in adjacent-swap based sorting methods (like bubble sort), this problem adopts the inversion count as the measure of the minimum swaps.

inputFormat

The input consists of a single line containing a string s of lowercase Latin letters.

Constraints:

• 1 ≤ |s| ≤ 10⁵

outputFormat

Output a single integer which is the minimum number of swaps required to sort the string into alphabetical order.

dcba

6