Test Case Pass: 54/54

blog_qwq_32b_coding_leetcode_question_response.cpp

class Solution {
public:
    int strongPasswordChecker(string password) {
        int n = password.length();
        
        // Check missing types
        bool hasLower = false, hasUpper = false, hasDigit = false;
        for (char c : password) {
            if (islower(c)) hasLower = true;
            else if (isupper(c)) hasUpper = true;
            else if (isdigit(c)) hasDigit = true;
        }
        
        int missingTypes = (!hasLower) + (!hasUpper) + (!hasDigit);
        
        // Case 1: Length < 6
        if (n < 6) {
            // We need max(6 - n, missingTypes) insertions
            return max(6 - n, missingTypes);
        }
        
        // Count repeating sequences
        int repeats = 0;
        vector<int> repeatLengths; // To store lengths of repeating sequences
        
        for (int i = 0; i < n;) {
            int j = i;
            while (j < n && password[j] == password[i]) j++;
            int len = j - i;
            
            if (len >= 3) {
                repeats += len / 3;
                repeatLengths.push_back(len);
            }
            
            i = j;
        }
        
        // Case 2: 6 <= Length <= 20
        if (n <= 20) {
            // We need max(missingTypes, repeats) replacements
            return max(missingTypes, repeats);
        }
        
        // Case 3: Length > 20
        int deletions = n - 20;
        
        // Sort repeating sequences by mod 3 value to optimize deletions
        vector<int> mod0, mod1, mod2;
        for (int len : repeatLengths) {
            if (len % 3 == 0) mod0.push_back(len);
            else if (len % 3 == 1) mod1.push_back(len);
            else mod2.push_back(len);
        }
        
        // Process deletions to minimize replacements needed
        // First delete chars from sequences where len % 3 == 0
        // Each deletion saves one replacement
        int remDeletions = deletions;
        int savedReplacements = 0;
        
        // For sequences with len % 3 == 0, delete 1 char to reduce replacements
        for (int& len : mod0) {
            if (remDeletions > 0) {
                int del = min(remDeletions, 1);
                len -= del;
                remDeletions -= del;
                savedReplacements += del;
            }
        }
        
        // For sequences with len % 3 == 1, delete 2 chars to reduce replacements
        for (int& len : mod1) {
            if (remDeletions > 0) {
                int del = min(remDeletions, 2);
                len -= del;
                remDeletions -= del;
                savedReplacements += (del == 2) ? 1 : 0;
            }
        }
        
        // For remaining repeating sequences, each 3 deletions reduce 1 replacement
        int totalLen = 0;
        for (int len : mod0) totalLen += len;
        for (int len : mod1) totalLen += len;
        for (int len : mod2) totalLen += len;
        
        savedReplacements += remDeletions / 3;
        
        // Calculate remaining replacements needed
        int remainingRepeats = repeats - savedReplacements;
        remainingRepeats = max(0, remainingRepeats);
        
        // We need deletions + max(missingTypes, remainingRepeats)
        return deletions + max(missingTypes, remainingRepeats);
    }
};

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