C++ 0ms solution with clear explanation


  • 0
    Z
    class Solution {
    public:
        int strongPasswordChecker(string s) {
            int n = s.size();
            // check whether each category of lowercase, uppercase, digit exists
            vector<int> missing(3,0);
            for (int i = 0; i < n; ++i) {
                if (s[i] >= 'a' && s[i] <= 'z') 
                    missing[0] = 1;
                else if (s[i] >= 'A' && s[i] <= 'Z') 
                    missing[1] = 1;
                else if (s[i] >= '0' && s[i] <= '9')
                    missing[2] = 1; 
            }
            // toInsert is how many categores to insert or replace, ranging 0-3
            int toInsert = 0;
            for (int i = 0; i < 3; ++i)
                if (missing[i] == 0)
                    ++toInsert;
            int res = 0;  // res is output result
            // n < 6 is easy; either 'toInsert' or (6-n) times insertion will fix it
            if (n < 6) 
                res = max(toInsert, 6-n);
            // n >= 6 and n <= 20; 1 replacement will fix 3 continuous letters; 
            // count the sequence of 3 repeating letters; result is max of sequence amounts and 'toInsert'
            else if (n <= 20) {
                int count = 1;
                for (int i = 1; i < n; ++i) {
                    if (s[i] == s[i-1]) 
                       ++count;
                    else
                       count = 1;
                    if (count >= 3) { 
                       ++res;
                       count -= 3;
                    }
                }
                res = max(res, toInsert);
            }
            // n > 20; 'toInsert' is how many to replace; 'toDelete' is extra letters; 
            else {
                // conts are the length of all repeating sequence >= 3
                vector<int> conts;
                int start = 0, length = 0, k = 1;
                while (k < n) {
                    while (k < n && s[k] == s[start]) 
                        ++k;
                    length = k-start;
                    start = k;
                    if (length >= 3) conts.push_back(length);
                }
                // use 'toInsert' to do replacements first; Because n > 20, replacement is better than insertion
                // 1 replacement will fix 3 continuous letters;
                // using greedy procedures, replace sequence longer than or equal to 5 first, 
               // then on sequences >= 4, last >= 3;
                // as long as sequence >= 5, the order doesn't matter;
                res = toInsert;
                // tmp is the critical length, decreasing from 5 to 3;
                // The following loop will be done in 3 passes, and it generally terminates early 
                // due to 'toInsert' <= 3
                // If there is no repeating sequence >= 3, 'toInsert' times replacement is still required
                int tmp = 5;
                while (toInsert > 0 && tmp >= 3) {
                    int i = 0;
                    while (toInsert > 0 && i < conts.size()) {
                        while (toInsert > 0 && conts[i] >= tmp) {
                           --toInsert;
                           conts[i] -= 3;
                        }
                        ++i;
                    }
                    --tmp;
                }
                // toDelete is the extra letters to delete
                int toDelete = n-20;
                res += toDelete;
                /* using greedy procedures: first, delete 1 letter from sequences with length%3 = 0, 
                i.e. 3, 6, 9 ...; second, delete 2 letters from length%3 = 1; 
                finally, all length%3 = 2 (first and second step ensures this);
                still 3 passes; tmp increase from 0 to 2;
                after deletion, repeating sequence >= 3 may still exist; 
                or, no repeating sequence left before finishing deletion;*/ 
                tmp = 0;
                while (toDelete > 0 && tmp < 3) {
                    // step is delete letters in every step; it is min of toDelete and tmp+1
                    int i = 0, step = 0; 
                    while (toDelete > 0 && i < conts.size()) {
                        while (conts[i] >= 3 && toDelete > 0 && conts[i]%3 == tmp) {
                           step = min(toDelete, tmp+1);
                           toDelete -= step;
                           conts[i] -= step;
                        }
                        ++i;
                    }
                    ++tmp;
                }
                // the following step is similar to the case n <= 20; 
               //if there is repeating sequence >= 3 left, count how many replacements required;
                for (int i = 0; i < conts.size(); ++i) 
                    res += conts[i]/3;
            }
            return res;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.