C++ O(n) Solution: A Case By Case Approach.


  • 0
    F

    Consider 3 cases:

    1. Password is too short
    2. Password is too long
    3. Password has the proper length.
      Case 1 and 3 are very trivial to solve.
      The main work happens with case 2.
      Here is the code:
    class Solution {
        bool has_lower = false, has_upper = false, has_digit = false;
        int checks = 0, sum_breaks = 0, r0count = 0, r1count = 0;
        vector<int> repeats;
        void signature(const string & s)
        {
            char c = '\0';
            int count = 0;
            for (int i = 0; i < s.size(); ++i)
            {
                if (isupper(s[i]))
                    has_upper = true;
                if (islower(s[i]))
                    has_lower = true;
                if (isdigit(s[i]))
                    has_digit = true;
                if (s[i] == c)
                    count ++;
                else{
                    if (count >= 3)
                        repeats.push_back(count);
                    c = s[i];
                    count = 1;
                }
            }
            if (count >= 3)
                repeats.push_back(count);
            checks = 3 - (has_lower + has_upper + has_digit);
            for (auto n : repeats)
            {
                if (n % 3 == 0)
                    r0count ++;
                if (n % 3 == 1)
                    r1count ++;
                sum_breaks += n / 3;
            }
        }
    public:
        int strongPasswordChecker(string s) {
            signature(s);
            if (s.size() < 6)
                return max(6 - (int)s.size(),  checks);
            if (s.size() <= 20)
                return max(sum_breaks, checks);
            int diff0 = s.size() - 20, diff = diff0;
            if (diff <= r0count)
                return max(sum_breaks - diff, checks) + diff0;
            sum_breaks -= r0count;
            diff -= r0count;
            if (diff <= r1count * 2)
                return max(sum_breaks - diff/2, 0) + diff0;
            sum_breaks -= r1count ;
            diff -= r1count * 2;
            if (diff <= sum_breaks * 3)
                return max(sum_breaks - diff/3, checks) + diff0;
            return checks + diff0;
        }
    };
    
    

Log in to reply
 

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