C++ 0ms O(n) 35 lines solution with detailed explanation


  • 25

    I've separated the problem into three cases:
    (1) s.length() < 6
    (2) 6 <= s.length() <= 20
    (3) s.length() > 20


    Let's look at case (1) first. If s.length() < 6, we know we have room to insert some more letters into s. Question is how to use the insertions effectively to reduce the number of potential replacements. I'm using a greedy approach for this one: I'm inserting one char between the second and third chars whenever I see a repetition of 3 letters as substring.

    e.g. Say we have room to insert some chars in string and we see a substring of "aaaa". I'll insert a 'B' to make it "aaBaa" to break the 3-char repetition, thus reducing potential replacement by 1. And we'll do this until we can't insert any more chars into s. When we reach this point, we'll start dealing with case (2)


    For case (2), I still follow a greedy approach. I'm simply searching for 3-char repetitions, and replacing one of the chars to break the repetition.
    e.g. If we see a substring of "aaaa", we'll make it "aaBa".

    My code deals with (1) and (2) together as s.length() <= 20.


    Case (3) is a little bit tricky because simple greedy doesn't work any more.
    When s.length() > 20, we want to delete some chars instead of inserting chars to reduce potential replacements. Question is the same: how to do it effectively? Let's do some observations here:

    Say len is the length of each repetition.
    (a) len % 3 only has three possible values, namely 0, 1 and 2.
    (b) Minimum number of replacements needed to break each repetition is len / 3.
    (c) Based on (a) and (b), we know that deletion can reduce replacements only if the deletion can change the value of len / 3
    (d) Based on (c), we know if we want to reduce 1 replacement, we need 1 deletion for len % 3 == 0, and 2 deletions for len % 3 == 1, and 3 deletions for len % 3 == 2.

    Given above observations, I simply implemented the solution to do (d).

    Also note that missing of upper case char, lower case char, or digit can always be resolved by insertion or replacement.


    I've pasted two versions of the solutions below, with and without comments, for easier reference.

    Without comments:

    class Solution {
    public:
        int strongPasswordChecker(string s) {
            int deleteTarget = max(0, (int)s.length() - 20), addTarget = max(0, 6 - (int)s.length());
            int toDelete = 0, toAdd = 0, toReplace = 0, needUpper = 1, needLower = 1, needDigit = 1;
            
            for (int l = 0, r = 0; r < s.length(); r++) {
                if (isupper(s[r])) { needUpper = 0; }               
                if (islower(s[r])) { needLower = 0; }
                if (isdigit(s[r])) { needDigit = 0; }
                
                if (r - l == 2) {                               
                    if (s[l] == s[l + 1] && s[l + 1] == s[r]) {     
                        if (toAdd < addTarget) { toAdd++, l = r; }  
                        else { toReplace++, l = r + 1; }           
                    } else { l++; }                                 
                }
            }
            if (s.length() <= 20) { return max(addTarget + toReplace, needUpper + needLower + needDigit); }
            
            toReplace = 0;                                         
            vector<unordered_map<int, int>> lenCnts(3);            
            for (int l = 0, r = 0, len; r <= s.length(); r++) {    
                if (r == s.length() || s[l] != s[r]) {
                    if ((len = r - l) > 2) { lenCnts[len % 3][len]++; } 
                    l = r;
                }
            }
            
            for (int i = 0, numLetters, dec; i < 3; i++) {                
                for (auto it = lenCnts[i].begin(); it != lenCnts[i].end(); it++) {
                    if (i < 2) {
                        numLetters = i + 1, dec = min(it->second, (deleteTarget - toDelete) / numLetters);
                        toDelete += dec * numLetters, it->second -= dec;                          
                        if (it->first - numLetters > 2) { lenCnts[2][it->first - numLetters] += dec; }   
                    }
                    toReplace += (it->second) * ((it->first) / 3);  
                }    
            }
    
            int dec = (deleteTarget - toDelete) / 3;                
            toReplace -= dec, toDelete -= dec * 3;
            return deleteTarget + max(toReplace, needUpper + needLower + needDigit);
        }
    };
    

    With comments:

    class Solution {
    public:
        int strongPasswordChecker(string s) {
            int deleteTarget = max(0, (int)s.length() - 20), addTarget = max(0, 6 - (int)s.length());
            int toDelete = 0, toAdd = 0, toReplace = 0, needUpper = 1, needLower = 1, needDigit = 1;
            
            ///////////////////////////////////
            // For cases of s.length() <= 20 //
            ///////////////////////////////////
            for (int l = 0, r = 0; r < s.length(); r++) {
                if (isupper(s[r])) { needUpper = 0; }               
                if (islower(s[r])) { needLower = 0; }
                if (isdigit(s[r])) { needDigit = 0; }
                
                if (r - l == 2) {                                   // if it's a three-letter window
                    if (s[l] == s[l + 1] && s[l + 1] == s[r]) {     // found a three-repeating substr
                        if (toAdd < addTarget) { toAdd++, l = r; }  // insert letter to break repetition if possible
                        else { toReplace++, l = r + 1; }            // replace current word to avoid three repeating chars
                    } else { l++; }                                 // keep the window with no more than 3 letters
                }
            }
            if (s.length() <= 20) { return max(addTarget + toReplace, needUpper + needLower + needDigit); }
            
            //////////////////////////////////
            // For cases of s.length() > 20 //
            //////////////////////////////////
            toReplace = 0;                                          // reset toReplace
            vector<unordered_map<int, int>> lenCnts(3);             // to record repetitions with (length % 3) == 0, 1 or 2
            for (int l = 0, r = 0, len; r <= s.length(); r++) {     // record all repetion frequencies
                if (r == s.length() || s[l] != s[r]) {
                    if ((len = r - l) > 2) { lenCnts[len % 3][len]++; } // we only care about repetions with length >= 3
                    l = r;
                }
            }
            
            /*
                Use deletions to minimize replacements, following below orders:
                (1) Try to delete one letter from repetitions with (length % 3) == 0. Each deletion decreases replacement by 1
                (2) Try to delete two letters from repetitions with (length % 3) == 1. Each deletion decreases repalcement by 1
                (3) Try to delete multiple of three letters from repetions with (length % 3) == 2. Each deletion (of three 
                letters) decreases repalcements by 1
            */
            for (int i = 0, numLetters, dec; i < 3; i++) {                
                for (auto it = lenCnts[i].begin(); it != lenCnts[i].end(); it++) {
                    if (i < 2) {
                        numLetters = i + 1, dec = min(it->second, (deleteTarget - toDelete) / numLetters);
                        toDelete += dec * numLetters;               // dec is the number of repetitions we'll delete from
                        it->second -= dec;                          // update number of repetitions left
                        
                        // after letters deleted, it fits in the group where (length % 3) == 2
                        if (it->first - numLetters > 2) { lenCnts[2][it->first - numLetters] += dec; }   
                    }
                    
                    // record number of replacements needed
                    // note if len is the length of repetition, we need (len / 3) number of replacements
                    toReplace += (it->second) * ((it->first) / 3);  
                }    
            }
    
            int dec = (deleteTarget - toDelete) / 3;                // try to delete multiple of three letters as many as possible
            toReplace -= dec, toDelete -= dec * 3;
            return deleteTarget + max(toReplace, needUpper + needLower + needDigit);
        }
    };
    

  • 7
    H

    @soamaaazing Thank you for the detailed explanations. My C++ version with all cases handled together.

    class Solution {
    public:
        int strongPasswordChecker(string s) {
            int n = s.size();
            int upper = 1, lower = 1, digit = 1;
            int toAdd = max(0, 6 - n);
            int toDel = max(0, n - 20);
            int rep = 0, add = 0, del = 0;
            // use to store consecutive letters based on len % 3
            // because lower value of len % 3 has precedence than
            // larger one on impact of reducing replacement number
            // len % 3 = 0, 1 deletion = 1 replacement aaa -> aa
            // len % 3 = 1, 2 deletion = 1 replacement aaaa -> aa
            // len % 3 = 2, 3 deletion = 1 replacement aaaaa -> aa
            // our goal is to use limited deletions to reduce
            // necessary replacement as many as possible
            vector<vector<int>> repeats(3);
            int j = 0;
            for (int i = 0; i <= n; i++) {
                if (i == n || s[i] != s[j]) {
                    int len = i - j;
                    if (i - j > 2) {
                        repeats[len % 3].push_back(len);
                    }
                    j = i;
                }
                if (i == n) break;
                if (isdigit(s[i])) digit = 0;
                if (isupper(s[i])) upper = 0;
                if (islower(s[i])) lower = 0;
            }
    
            for (int i = 0; i < 3; i++) {
                auto v = repeats[i];
                for (int j = 0; j < v.size(); j++) {
                    if (i < 2) {
                        if (toAdd - add > 0) { // current length less than 6
                            add++;
                            v[j] -= i+1;
                        }
                        if (toDel - del > 0) { // current length larger than 20
                            del += i+1; // del could be larger than 'toDel' which will be made up below 
                            v[j] -= i+1;
                        }
                    }
                    rep += v[j] / 3;
                }
            }
            if (toDel - del > 0) {
                /* after v[j] -= i+1; in the for loop above, the length of all consecutive letters
                * handled by rep += v[j] / 3; meets len % 3 = 2, for example:
                * case len % 3 = 0 : "aaaaaa" => "aaaaa", rep get 1 credit via rep += v[j] / 3;
                * case len % 3 = 1 : "aaaaaaaaaa" => "aaaaaaaa", rep get 2 credits via rep += v[j] / 3;
                * now, there could be more letters to delete, i.e. toDel - del > 0
                * so, we need to take the credit given to rep back
                * because at the time rep got the credit, len % 3 is 2, to reduce 1 rep, we need to
                * do 3 deletions, that is how the number '3' comes out. 
                * certainly, if rep didn't get enough credits, we shouldn't overdraw, i.e. minimum rep
                * should be 0.
                */
                rep = max(0, rep - (toDel - del) / 3);
            }
            else {
                rep += del - toDel; // make up. del - toDel could only be 0 or 1
            }
    
            return toDel + max(toAdd + rep, upper + lower + digit);
        }
    };
    

  • 2
    P

    @soamaaazing said in C++ 0ms O(n) 35 lines solution with detailed explanation:

    toDelete -= dec * 3;

    I think it should be toDelete += dec * 3;


  • 0
    J

    @Hcisly

    Do you mind to explain the last line:

    return toDel + max(toAdd + rep, upper + lower + digit);
    

    I am thinking that:
    (a) toDel + toAdd + rep: for case <= 20
    (b) toDel + upper + lower + digit: for case > 20

    Am I right?


  • 2
    H

    @jtee toDel and toAdd won't be non-zero at same time, so it doesn't matter to put them together.

    for case > 20, toDel is the required operations, toAdd = 0. So the last line equal to return toDel + max(rep, upper + lower + digit); If deletions already get rid of all repeats, rep will be 0, in that case, we may still need more replacements to meet upper/lower/digit requirement, so use max(rep, upper + lower + digit) to pick up the larger one.

    for case < 6, toDel = 0, toAdd > 0. it equals to return max(toAdd + rep, upper + lower + digit); . Because both addition and replacement could help to meet upper/lower/digit requirement. we just simply pick up the larger one.

    Hope that helps


  • 0
    J

    @Hcisly

    That's a very impressive explanation! Thanks! :)


  • 0
    R

    @Hcisly, could I ask in the line

    rep = max(0, rep - (toDel - del) / 3);

    how does the number 3 come out?
    Thanks so much!


  • 0
    H

    @runxinhe Put more comments inline. Hope that helps


  • 0
    R

    @Hcisly Great! I got it now. Thanks so much!


  • 0
    M

    the solution is really not trivial. I don't think I can finish it easily

    Can we solve this problem using edit distance.
    I mean, we construct a qualify password using some kind of search and then calculate the edit distance,
    then we choose the minimum edit distance.

    This is just my guess.


  • 0
    H

    Hi @Hcisly ,

    I think your algorithm is only correct when the minimum size is 6. If you change minimum size to 9, and run with example "aaaaaa", you would get 4 instead of the correct answer 3 ("aabaabaab").

    I would suggest changing the logic to

        for (int i = 0; i < 3; i++) {
            auto v = repeats[i];
            for (int j = 0; j < v.size(); j++) {
                if (i < 2 && toDel - del > 0) { // current length larger than 20
                        del += i+1; // del could be larger than 'toDel' which will be made up below 
                        v[j] -= i+1;
                }
                else while (toAdd - add > 0 && v[j] >= 3) { // we should add new chars as long as we need to and the sequence is larger than 3
                    add++;
                    v[j] -= 2; // each addition could decrease length by 2, even though it might not decrease rep
                }
                rep += v[j] / 3;
            }
        }

Log in to reply
 

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