cpp sln


  • 0
    M
    int getCountForCharType(const string& s)
    {
        // check lowercase, uppercase and digit
        bool lc = false, uc = false, digit = false;
        for (int i = 0; i < s.length(); i++)
        {
            if ( '0' <= s[i] && s[i] <= '9')
            {
                digit = true;
            }
            if ( 'A' <= s[i] && s[i] <= 'Z')
            {
                uc = true;
            }
            if ( 'a' <= s[i] && s[i] <= 'z')
            {
                lc = true;
            }
        }
        return lc + uc + digit;        
    }
    
    int checkRowLetter(const string& s, priority_queue<int, vector<int>, Compare>& dupLetterQ)
    {
        // check three letter
        char curChar = s[0];
        int charCount = 1;        
        int changeFordup = 0;
        for (int i = 1; i < s.length(); i++)
        {
            if (curChar == s[i])
            {
                charCount++;
            }
            else
            {
                if (charCount >= 3)
                {
                    changeFordup += charCount / 3;
                    dupLetterQ.push(charCount);
                }
                curChar = s[i];
                charCount = 1;
            }
        }
        if (charCount >= 3)
        {
            changeFordup += charCount / 3;
            dupLetterQ.push(charCount);
        }
        return changeFordup;
    }
    
    int strongPasswordChecker(string s) {
        if (s.empty())
        {
            return 6;
        }
        
        int caseCount = getCountForCharType(s);
    
        priority_queue<int, vector<int>, Compare> dupLetterQ;
        int changeFordup = checkRowLetter(s, dupLetterQ);
        
        // if we do not delete char for longger string.
        if (s.length() <= 20)
        {
            return max(max(3 - caseCount, 6 - (int)s.length()), changeFordup);
        }
        
        
        // since string longer than 20, we need delete chars, and we first try to delete those char in dup, that minmize changing.
        int countToDel = s.length() - 20;
        int i = 0;
        while (!dupLetterQ.empty() && i < countToDel)
        {
            int top = dupLetterQ.top();
            dupLetterQ.pop();
            top -= 1;
            if (top >= 3)
            {
                dupLetterQ.push(top);
            }
            i++;
        }
            
        // if no dup letter after delete, we just need change more letter to satisify the digit rule.
        if (dupLetterQ.empty())
        {
            return countToDel + 3 - caseCount;
        }
            
        // otherwise, we need consider remove rest dup and also need sitisify the digit rule
        changeFordup = 0;
        while (!dupLetterQ.empty())
        {
            changeFordup += dupLetterQ.top() / 3;
            dupLetterQ.pop();
        }
        return max(changeFordup, 3 - caseCount)  + countToDel;
    
    }
    

    class Compare
    {
    public:
    bool operator () (int a, int b)
    {
    return a % 3 > b % 3;
    }
    };


Log in to reply
 

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