相邻字符交换

题目描述

给定一个字符串 $S$,它是 atcoder 的一个排列。

你可以对 $S$ 执行以下操作 $0$ 次或多次:

• 选择 $S$ 中两个相邻的字符并交换它们。

求使 $S$ 变为 atcoder 所需的最少操作次数。

输入格式

$S$

输出格式

输出答案,答案为一个整数。

样例

catredo

8

可以通过如下 $8$ 次操作使 $S$ 变为 atcoder:

catredo $\rightarrow$ [ac]tredo $\rightarrow$ actre[od] $\rightarrow$ actr[oe]d $\rightarrow$ actro[de] $\rightarrow$ act[or]de $\rightarrow$ acto[dr]e $\rightarrow$ a[tc]odre $\rightarrow$ atcod[er]

这是可实现的最少操作次数。

atcoder

0

此时字符串 $S$ 已经是 atcoder。

redocta

21

数据范围

• $S$ 是 atcoder 的一个排列。