P14905 [NHSPC 2024] 分漆付款

兔子是「兔兔建設」的社長。最近公司的建設進度不如預期，經過兔子社長的調查後，發現原因出在負責運送油漆的粽子離職了！於是兔子社長決定雇用猩猩來完成原本粽子的工作。另外，在調查過程中兔子社長還發現，假如能在油漆搬運抵達之後將其進行分類，可以進一步提升裝潢部門的效率。於是兔子社長藉此機會，也將此任務安排給猩猩來完成。 根據規定，搬運完成的油漆桶會被擺放成一列。由於油漆桶非常重，猩猩每次只能將兩桶相鄰的油漆交換位置。兔子社長給猩猩的要求是將所有相同顏色的油漆桶擺在一起。舉例來說，假設油漆總共有 7 桶，其顏色分為紅綠藍三種，分別以 `R`、`G`、`B` 表示，而初始時此 7 桶油漆從左到右的排列為：`RRGGBGB`，則猩猩只需要一次操作，便能把油漆桶排列為 `RRGGGBB`。又若初始時油漆桶的排列為：`GRRGBRB`，則猩猩最少只要三次操作，便能把油漆桶排列為 `GGRRRBB`。 狡猾的兔子社長決定根據完成任務所需最少的交換次數來支付猩猩的薪水，假如給定油漆桶初始的排列，你能幫助猩猩算出最少的交換次數，來估計她應得的薪水嗎？

$$S$$ - $S$ 為一個字串，代表油漆桶的排列順序，其中相同字符表示相同顏色的油漆桶，不同字符代表不同顏色。

$$m$$ - $m$ 代表最少的交換次數。

### 測資限制 * $1 \le |S| \le {10}^{6}$。 * $1 \le \textrm{distinct}(S) \le 7$。 * 字串 $S$ 由大小寫英文字母組成。 * $\textrm{distinct}(S)$ 代表字串 $S$ 中字元種類的數量。 ### 評分說明 本題共有三組子任務，條件限制如下所示。 每一組可有一或多筆測試資料，該組所有測試資料皆需答對才會獲得該組分數。 | 子任務 | 分數 | 額外輸入限制 | | :------: | :----: | ------------ | | 1 | 21 | $\textrm{distinct}(S) \le 2$。 | | 2 | 26 | $1 \le \lvert S\rvert \le {10}^{3}$，$\textrm{distinct}(S) \le 3$。 | | 3 | 53 | 無額外限制。 |