LeetCode刷题实战420：强密码检验器-轻识

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选！

今天和大家聊的问题叫做 强密码检验器，我们先来看题面：

https://leetcode-cn.com/problems/strong-password-checker/

一个强密码应满足以下所有条件：

由至少6个，至多20个字符组成。

至少包含一个小写字母，一个大写字母，和一个数字。

同一字符不能连续出现三次 (比如 "...aaa..." 是不允许的, 但是 "...aa...a..." 是可以的)。

编写函数 strongPasswordChecker(s)，s 代表输入字符串，如果 s 已经符合强密码条件，则返回0；否则返回要将 s 修改为满足强密码条件的字符串所需要进行修改的最小步数。

插入、删除、替换任一字符都算作一次修改。

解题

http://www.manongjc.com/detail/20-zosdnuezjvotflt.html

这是一道数学题。

连续字符串删除和插入的方式代价高，尽量使用替换。如何理解呢？对于任意>=3的连续串长度为s，所需要的替换次数为s//3，

而使用插入(s-1)/2次操作和删除s-2次。插入和删除相结合还是比替换要慢。

对于长度>=3的连续串，每个修改次数为s//3, s为连续串的长度，记录总的连续串修改次数为n_modify

记录确实字符个数为n_lack

length<6，返回max(6-len(s), n_lack)

length<=20，返回max(n_modify, n_lack)

length>20，此时一定要删除字符的长度为n_delete = len(s) - 20

我们知道连续串可以通过删除字符来减少n_modify。我们肯定优先删除连续串。对于不同长度的连续串，有这样的特性。

3n，删除一个字符，就可以减少一次替换

3n+1, 删除两个字符，减少一次替换

3n+2, 删除三个字符，减少一个替换

要使得最终结果最小，我们优先考虑3n，多出来的继续考虑3n+1，和3n+2。最终剩下来的都是3n+2，即如果还有剩余就全部用来减少3n+2的替换次数。

class Solution:
    def strongPasswordChecker(self, s: str) -> int:
        cnt = [0]*3 # 3n, 3n+1, 3n+2

        a , A, num = 1, 1, 1
        i = 0
        n_modify = 0
        while i < len(s):
            c = s[i]
            length = 1
            if s[i] >= '0' and s[i] <= '9':
                num = 0
            elif s[i] >= 'a' and s[i] <= 'z':
                a = 0
            elif s[i] >= 'A' and s[i] <= 'Z':
                A = 0
            i += 1            
            while i < len(s) and s[i] == c:
                i += 1
                length += 1 
            if length >= 3:
                n_modify += length//3
                cnt[length%3] += 1
                
        n_lack = a + A + num
        if len(s) < 6:
            return max(n_lack, 6-len(s))
        if len(s) <= 20:
            return max(n_lack, n_modify)

        n_delete = len(s) - 20

        if n_delete <= cnt[0]:
            return max(n_modify - n_delete, n_lack) + n_delete

        if (n_delete - cnt[0]) <= 2*cnt[1]:
            return max(n_modify - cnt[0]- (n_delete-cnt[0])//2, n_lack) + n_delete

        if (n_delete - cnt[0] - 2*cnt[1]) <= 3 * cnt[2]:
            return max(n_modify - cnt[0] - cnt[1]- (n_delete - cnt[0] - 2*cnt[1])//3, n_lack) + n_delete;
        return max(n_modify - cnt[0] - cnt[1] - cnt[2] - (n_delete - cnt[0] - 2*cnt[1] 
                   -3*cnt[2])//3, n_lack) + n_delete;