题目描述

狐狸次郎和三郎正在玩一维翻转棋。在一维翻转棋中，棋盘上的棋子只有黑色或白色，所有棋子排成一行。每次可以在最左端或最右端新下一个棋子。与普通翻转棋一样，例如下一个白色棋子时，如果夹住了黑色棋子，被夹住的黑色棋子会变成白色。

游戏进行到一半时，三郎突然有急事离开了。这时，棋盘的状态用字符串 $S$ 表示。棋盘上共有 $|S|$（字符串长度）个棋子，从左到右第 $i$ 个棋子的颜色由 $S$ 的第 $i$ 个字符决定，若为 B 则为黑色，若为 W 则为白色。

次郎想通过尽可能少地下棋，使得所有棋子的颜色都相同。请你求出最少需要下多少个棋子，才能使所有棋子颜色相同。

输入格式

输入为一行，包含一个字符串 $S$。

输出格式

输出使所有棋子颜色相同所需下的最少棋子数。

样例 1

输入

BBBWW

输出

1

样例 2

输入

WWWWWW

输出

0

样例 3

输入

WBWBWBWBWB

输出

9

说明/提示

限制条件

• $1 \leq |S| \leq 10^5$
• $S$ 只包含字符 B 或 W

样例解释 1

例如，在右端下一个黑色棋子，可以将所有白色棋子变为黑色。或者在左端下一个白色棋子，也可以将所有棋子变为同一种颜色。无论哪种情况，只需下 $1$ 个棋子即可使所有棋子颜色相同，因此输出 $1$。

样例解释 2

如果一开始所有棋子颜色都相同，则无需再下棋。

由 ChatGPT 4.1 翻译