[LeetCode] Strong Password Checker

这道题比较麻烦，但是我们可以明确要分情况考虑：

1. 如果len < 6，我们只需要考虑insert和replace
2. 如果len >= 6 && len <= 20，我们只需要考虑replace
3. 如果len > 20，我们要考虑delete和replace

对于第一种情况，我们先考虑insert，insert就要insert 6 - len个字符，假设为了满足条件2我们需要insert或者replace k(k = 1/2)个新的字符种类，那么我们只需要max(6 - len, k)的步骤就可以满足所有条件。对于情况3，若连续子串长度为3或者4，我们直接插入一个字符就必定满足，而max(6 - len, k)肯定>= 1；对于长度为5的连续子串，我们插入一个字符无法使其满足条件3，但是注意条件2，其肯定还缺两种类型的字符，所以我们插入之后再replace一个，需要两步，2 = max(6 - 5, 2)。

对于第二种情况，我们只需要考虑replace，首先第一种条件已经满足。那么满足2的条件假设我们需要replace k(k = 1/2)个字符。为了满足条件3假设我们需要replace m个字符，那么对于一个长度为subLen的连续子串我们需要replace subLen / 3个字符使其满足条件，比如aaaaa我们只需要变成aabaa即可。那么我们只需要取max(k, m)即可。

对于第三种情况会有点复杂，因为delete也可以减少连续重复子串的数量，因为我们无论如何都需要删除len - 20个字符，所以我们先考虑delete的情况，那么我们如何delete呢。len % 3有0，1，2三种情况，由于replace的m个字符取决于len / 3，我们要尽量减少为了满足条件3而replace的m个字符，那么对于这三种情况，分别删除1，2，3个字符可以使m减少1。显然我们从len % 3 = 0的情况开始删一直到len % 3 = 2。当然我们要keep track of delete字符的数量，当期数量不足的时候我们停止。当处理完len % 3 =1 和2的情况的时候，所有剩下的连续重复子串的长度都为len % 3 = 2我们就看剩下的要删除的字符还能够将m减少多少，现在每减少一个m都需要删除3个字符。最后我们在考虑还有多少个字符需要replace来满足条件3和条件2，也就是max(k, m)，m为更新之后的m。

时间复杂度O(n)，空间复杂度O(n)，代码如下：