Amazon VO 面试真题解析：最少翻转次数使所有 X 在所有 Y 之前

You are given a string consisting of the letters x and y, such as xyxxxyxyy.

In addition, you have an operation called flip, which changes a single x to y or vice versa. Determine how many times you would need to apply this operation to ensure that all x‘s come before all y‘s.

In the preceding example, it suffices to flip the second and sixth characters, so you should return 2.

这道题要求把只由 x 和 y 组成的字符串变成“所有 x 都在所有 y 前面”的形式，并且每次只能翻转一个字符。核心思路通常是线性扫描：统计当前位置左侧出现了多少个 y，以及右侧还剩多少个 x，把某个位置作为分界点时，需要翻转的次数就是左边的 y 数加上右边的 x 数，答案取最小值。这个问题本质上是在找一个最优分割点，因此可以用前缀统计或一次遍历完成，时间复杂度为 O(n)，空间复杂度可做到 O(1)。