My C++ solution


  • -1
    T

    class Solution {
    public:
    int num_types(const string& s){
    int res = 0;
    bool has_l = false;
    bool has_u = false;
    bool has_d = false;
    for(const auto& c: s){
    if(c>='0' && c<='9')
    has_d = true;
    else if (c>='A' && c<='Z')
    has_u = true;
    else if (c>='a' && c<='z')
    has_l = true;
    }
    return has_l + has_u + has_d;
    }
    // Returns the MINIMUM changes for s[begin:], curr_n is the current length of the modified string.
    int helper(const string& s, int begin, int types, int curr_n) {
    int steps = 0;
    // Check the three repeating characters. Choose replace/delete/insert based on the length.
    for(int i= begin+1;i+1< s.length();){
    // Pattern "aaa".
    if(s[i]==s[i-1] && s[i]==s[i+1]){
    // if curr_n < 6, insert after i.
    if(curr_n < 6) {
    steps++;
    curr_n++;
    i+=2;
    types++;
    } else if (curr_n > 20) {
    // Remove the i-1 or replace at i+1.
    return steps + 1 + std::min(helper(s, i, types, curr_n-1), helper(s, i+2, types+1, curr_n));
    } else { // Replace the i+1
    steps++;
    i+=3;
    types++;
    }
    } else {
    i++;
    }
    }
    // There are no repeating "aaa" patterns now.
    if(curr_n<6) { // insert.
    steps += (6-curr_n);
    types += (6-curr_n);
    curr_n = 6;
    } else if (curr_n >20) { // Delete.
    steps += (curr_n-20);
    curr_n = 20;
    }
    // Length has meet the requirements. Check types of characters.
    if(types<3)
    steps += (3-types);
    return steps;
    }
    int strongPasswordChecker(string s) {
    return helper(s, 0, num_types(s), s.length());

    }
    

    };


  • 0

    @treeguard Format the code, please.


Log in to reply
 

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