class Solution {
public:
    int strongPasswordChecker(string s) {
        //toReplace represent number of replace we can do to suffice case 3
        int len = s.size(), needLower = 1, needUpper = 1, needNum = 1, left = 0, toReplace = 0;
        //let say subLen is length of repeating chars with length more than 2
        //toReplace only depends on subLen / 3
        //So we use map to count subLen % 3 == 0, subLen % 3 == 1 and subLen % 3 == 2
        //when deleteing, we delete from subLen % 3 == 0 since it can reduce toReplace by deleting least characters
        vector<unordered_map<int, int>> counts(3);
        for(int i = 0; i <= len; ++i)
        {
            char c = s[i];
            if(islower(c))needLower = 0;
            if(isupper(c))needUpper = 0;
            if(isdigit(c))needNum = 0;

            if(i >= len || c != s[left])
            {
                int subLen = i - left;
                if(subLen >= 3)
                {
                    ++counts[subLen % 3][subLen];
                    toReplace += subLen / 3;
                }
                left = i;
            }
        }

        if(len < 6)return max(6 - len, needUpper + needLower + needNum);
        else if(len <= 20)return max(toReplace, needUpper + needLower + needNum);
        else
        {
            //delete first, then replace
            int toDelete = len - 20, totalDeleted = toDelete;
            toReplace = 0;
            for(int i = 0; i < 3; ++i)
            {
                //first check deleting 1 char
                //then check deleting 2 and deleting 3
                for(auto&& p : counts[i])
                {
                    if(i < 2)
                    {
                        int canDelete = min(p.second, toDelete / (i + 1));
                        toDelete -= canDelete * (i + 1);
                        p.second -= canDelete;
                        //now three will be only len % 3 == 2
                        if(p.first - (i + 1) > 2)counts[2][p.first - (i + 1)] += canDelete;
                    }
                    //now we have all repeating substring with len % 3 == 2, counting it
                    toReplace += p.second * (p.first / 3);
                }
            }
            //if we have more char can delete, delete to reduce toReplace
            toReplace -= (toDelete / 3);
            return totalDeleted + max(toReplace, needUpper + needLower + needNum);
        }
    }
};