强密码检查器

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

We know that replace is the most effective way to change the password. But
If len>20, we at lease need to delete length-20 characters. The deletion can work as follow:
Assume the length of repeating characters is n, there are 3 cases for repeating characters:n%3==0, n%3==1, n%3==2.

n%3==0 if n=3,6,9… If String s=“aaa”,delete the last one and s=“aa”. If String s=“aaaaaa”, replace one character and delete the last one works and s="aabaa ". If String s=“aaaaaaaaa”, replace two character and delete the last one works and s="aabaacaa ".

n%3==1 if n=4,7,10… If String s=“aaaa”,delete the last 2 characters and s=“aa”. If String s=“aaaaaaa”, replace the one character and delete the last two works and s="aabaa ".

n%3==2 if n=5,8,11… If String s=“aaaaa”,delete the last 3 characters and s=“aa”. If String s=“aaaaaaaa”, replace the one character and delete the last three works and s="aabaa ".

Always delete the last few characters and use the replace most of times. One deletion works for one n%3==0, two deletion works for one n%3==1, and three deletion works for one n%3==2. The deletion first used for n%3==0 cases then n%3==1 and finally n%3==2.

int strongPasswordChecker(string s) {
    const int N = s.size();
    int needLower = 1, needUpper = 1, needDigit = 1;
    int modifyOp = 0;
    vector<int> type(3, 0);
    // 长len>=3的重复子串，按照len%3分三类，用type[len%3]计数
    // 假设已进行过修改操作，比如aaaaaa已修改成aa#aa#
    // len%3==0这类子串，末尾可用1个删除省掉1个修改，比如 aa#aa#   => aa#aa
    // len%3==1这类子串，末尾可用2个删除省掉1个修改，比如 aa#aa#a  => aa#aa
    // len%3==2这类子串，末尾可用3个删除省掉1个修改，比如 aa#aa#aa => aa#aa
    for (int i = 0, j; i < N; i = j) {
        if(islower(s[i])) needLower = 0;
        else if(isupper(s[i])) needUpper = 0;
        else if(isdigit(s[i])) needDigit = 0;

        j = i + 1;
        while (j < N && s[j] == s[i]) j++;
        int len = j - i;
        if (len >= 3) {
            modifyOp += len / 3; // 每3个字母修改第3个
            type[len % 3]++;
        }                
    }

    int needLUD = needLower + needUpper + needDigit;
    if (N < 6) return max(6 - N, needLUD); // 只需插入操作
    if (N <= 20) return max(modifyOp, needLUD); // 只需修改操作
    // N > 20
    const int needDelete = N - 20; // 需要的删除操作数
    // 用删除操作取代部分修改操作，可以省掉多少修改操作？
    int deleteOp = needDelete;
    if (deleteOp <= type[0]) {
        modifyOp -= deleteOp;
    } else {
        modifyOp -= type[0];
        deleteOp -= type[0];
        // len%3==1这类子串要省掉type[1]个修改，需要2*type[1]个删除
        if (deleteOp <= 2 * type[1]) {
            modifyOp -= deleteOp / 2;
        } else {
            modifyOp -= type[1];
            deleteOp -= 2 * type[1];
            // 剩下的deleteOp都作用在len%3==2这类子串上
            modifyOp -= deleteOp / 3;    
        }
    }
    // modifyOp可以同时解决needLUD问题，所以用 max(modifyOp, needLUD)
    return needDelete + max(modifyOp, needLUD);        
}

algo-aha

强密码检查器