Problem 1

修改后的有序01串一共只有|S|+1种可能情况。我们可以枚举最后的有序01串，那么就可以通过逐位比较计算出需要修改的字符数目。复杂度O(N^2)。

如果我们通过预处理，计算出初始01串的每个前缀和后缀分别有多少个0，多少个1。那么我们就不用O(N)的逐位比较，可以直接计算出需要修改的字符数目。

Problem 2

贪心。首先我们需要分析INVALID的充分必要条件。容易看出充要条件是S中某个字符的数目超过了(|S|+1)/2。

于是我们可以采用贪心策略来找到字典序最小的解：对于输入的S，首先判断是否INVALID。如果不是INVALID，我们按照'a'-'z'的顺序枚举第一个字符c，如果除去c之后，S的剩余的字符仍然不是INVALID，那么我们就把第一个字符定为c。这样依次确定每一位即可。

Problem 3

宽度优先搜索。这类题目的关键在于状态的设计。就本题来说，我们需要把当前获得了哪些钥匙也表示进状态里。具体来说，当前状态是一个三元组(x, y, keys)，表示小Hi在(x, y)这个位置，获得的钥匙集合是keys。 钥匙最多有5把，所以一共有2^5种可能。再加上100 x 100的位置状态，一共有320000种状态。

需要注意的是一些特殊情况的处理。比如钥匙在上锁的房间里，出口在上锁的房间等。