Is my solution correct?


  • 0

    How I think:

    1. record if any absent in lower/uppercase/ number. (toFill)
    2. record the length of consecutive same characters with len>=3. (oops[3])
    3. while the length <6, add a character, and at the same time: use a mandatory but absent character to split a consecutive sequence apart.
    4. while the length > 20, remove a character from a consecutive sequence in the following order : len%3 ==0, len%3 ==1, len%3 ==2.
    5. replace a character to split a consecutive sequence, using mandatory but absent character first.

    It takes linear time and evaluated as accepted with 0ms.

    The code:

    class Solution {
    public:
        template<char A, char B> bool inRange(char ch) {return ch >= A && ch <= B;}
        int strongPasswordChecker(string s) {
            char flags[4] = {};
            int toFill = 3;
            vector<int> oops[3];
            int cnt =0;
            char tmp = '\0';
            for(char ch : s) {
                if(inRange<'0','9'>(ch) && !flags[0]) flags[0] = 1, --toFill;
                else if(inRange<'a','z'>(ch) && !flags[1]) flags[1] = 1, --toFill;
                else if(inRange<'A','Z'>(ch) && !flags[2]) flags[2] = 1, --toFill;
                if(tmp==ch)++cnt;
                else {
                    if(cnt>=3) oops[cnt%3].push_back(cnt);
                    cnt = 1;
                    tmp = ch;
                }
            }
            if(cnt>=3) oops[cnt%3].push_back(cnt);
            int ret = 0;
            int sz = s.size();
            while(sz<6) {
                ++sz;
                ++ret;
                --toFill;
                remove(oops,3);
            }
            while(sz>20) {
                --sz;
                ++ret;
                remove(oops,1);
            }
            int cut = 0;
            for(int i=0;i<3;++i) for(int x : oops[i]) cut += x/3;
            return ret + max(cut,toFill);
        }
        static void remove(vector<int> cnts[3], int dec) {
            int tmp = 0;
            for(int i=0;i<3;++i) {
                if(cnts[i].empty())continue;
                tmp = cnts[i].back()-dec;
                cnts[i].pop_back();
                break;
            }
            if(tmp>2) cnts[tmp%3].push_back(tmp);
        }
    };
    

  • 0
    T

    @leo.lai.944 said in Is my solution correct?:

    while the length > 20, remove a character from a consecutive sequence in the following order : len%3 ==0, len%3 ==1, len%3 ==2.

    I haven't read your code carefully. But when the length exceeds 20, and consecutive same characters are encountered, remove is not always the optimal solution. Replace can also produce optimal solution.

    For example:
    aaaabbaaabbaaa123456A

    when processing first "aaaa", you can either remove one or replace the third char.


  • 0

    @treeguard Thanks for your reply.
    I think it is always in need for removals until length <=20. My solution doesn't process 'aaaa' first in your example, but removes an entry from 'aaa' because of the order with 'len%3 == 0' on top priority.
    Replacement in 'aaaa' does happen in step 5. So I think your concern is correct and my solution doesn't cause conflict against your idea.


Log in to reply
 

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