In this Leetcode Strong Password Checker problem solution A password is considered strong if the below conditions are all met:

  1. It has at least 6 characters and at most 20 characters.
  2. It contains at least one lowercase letter, at least one uppercase letter, and at least one digit.
  3. It does not contain three repeating characters in a row (i.e., "...aaa..." is weak, but "...aa...a..." is strong, assuming other conditions are met).

we have given a string password, return the minimum number of steps required to make password strong. if the password is already strong, return 0.

In one step, you can:

  1. Insert one character to password,
  2. Delete one character from password, or
  3. Replace one character of password with another character.

Leetcode Strong Password Checker problem solution


Problem solution in Python.

class Solution:
    def strongPasswordChecker(self, password: str) -> int:
        def type_(c):
            if c.isdigit(): return 0
            if c.isupper(): return 1
            return 2
        
        numTypes = len(set(type_(c) for c in password))
        if len(password) <= 4: return (6 - len(password))
        if len(password) == 5: return max(1, 3 - numTypes)
		
        lengthOfSequences = [len(list(li)) for _, li in itertools.groupby(password)]
        numReplace = sum(length // 3 for length in lengthOfSequences)   
        if len(password) <= 20: return max(3 - numTypes, numReplace)
        
        numDelete = len(password) - 20
        for i, length in enumerate(lengthOfSequences):
            if length >= 3 and length % 3 == 0 and numReplace > 0 and numDelete >= 1:
                lengthOfSequences[i] -= 1
                numReplace -= 1
                numDelete -= 1
                    
        for i, length in enumerate(lengthOfSequences):
            if length >= 3 and length % 3 == 1 and numReplace > 0 and numDelete >= 2:
                lengthOfSequences[i] -= 2
                numReplace -= 1
                numDeletes -= 2
        
        numReplace -= min(numDelete // 3, sum(length // 3 for length in lengthOfSequences))
        return len(password) - 20 + max(numReplace, 3 - numTypes)



Problem solution in Java.

class Solution {
   
   
    public static int strongPasswordChecker(String s) {
        int deletions = 0, finalCounter = 0, insertions = 0, repeating = 1, changesSum;
        int replacements = 0, length = s.length();
        boolean digit, lowerCase, upperCase;
        digit = lowerCase = upperCase = false;
        ArrayList<Integer> arr = new ArrayList<>();

        for (int i = 0; i < length; i++) {
            if (i > 19)
                deletions++;
            if (Character.isLowerCase(s.charAt(i)))
                lowerCase = true;
            if (Character.isUpperCase(s.charAt(i)))
                upperCase = true;
            if (Character.isDigit(s.charAt(i)))
                digit = true;
            if (i > 0) {
                if (s.charAt(i) == s.charAt(i - 1))
                    repeating++;
                else {
                    if (repeating > 2)
                        arr.add(repeating);
                    repeating = 1;
                }
            }
        }
        if (repeating > 2)
            arr.add(repeating);
        if (digit)
            insertions++;

        if (upperCase)
            insertions++;

        if (lowerCase)
            insertions++;
        insertions = 3 - insertions;

        if(deletions > 0 && arr.size() > 0)
            arr = arrayReducer(arr, deletions);
        changesSum =listSum(arr);
        finalCounter = deletions + changesSum;

        if(insertions > 0){
            if(changesSum >= insertions)
                insertions = 0;
            else
                insertions = insertions - changesSum;
            }
        if(s.length() < 6) {
            if(insertions < 6- (s.length()))
                insertions = insertions + (6 - s.length() - insertions);
            if(insertions > changesSum)
                insertions = insertions - changesSum;
        }
        finalCounter = finalCounter + insertions;

            return finalCounter;
    }

    public static int listSum (ArrayList<Integer> arr){
        int sum = 0;
        for(int i = 0; i < arr.size();  i ++ )
            sum = sum + (arr.get(i)/3);

        return sum;

    }
    public static ArrayList arrayReducer(ArrayList<Integer> arr, int i) {
        int mod;
        int current, counter = 0, flag = arr.size() + 1;
        while(i>0) {
            mod = counter%3;
            for(int x = 0; x <arr.size(); x++) {
                if( flag == 0 )
                    return arr;
                current = arr.get(x);
                if (current % 3 == mod) {
                    if (i >= (mod + 1)) {
                        i = i - (mod + 1);

                        arr.set(x, current - (mod + 1));
                    } else{
                        flag--;
                        if (mod == 0)
                        return arr;
                    }
                    if (i == 0)
                        return arr;


                }
                if(i < (mod + 1))
                    if(mod == 0)
                        return arr;
            }
            counter++;
        }
        return arr;
    }



}


Problem solution in C++.

class Solution {
public:
    int strongPasswordChecker(string s) {
        // For diversity requirement.
        bool lower_case(false), upper_case(false), digit(false);
        
        // For repeats.
        std::vector<int> run_lengths;

        char curr;
        int run_length(0);
        for (int i = 0; i < s.size(); ++i) {
            // Do we need new characters.
            if (s[i] >= 'a' && s[i] <= 'z') {
                lower_case = true;
            } else if (s[i] >= 'A' && s[i] <= 'Z') {
                upper_case = true;
            } else if (s[i] > '0' && s[i] <= '9') {
                digit = true;
            }
            
            // Repeats.
            if (i == 0) {
                curr = s[0];
                run_length = 1;
                continue;
            }
            if (s[i] == curr) {
                ++run_length;
            } else {
                if (run_length >= 3) {
                    run_lengths.push_back(run_length);
                }
                curr = s[i];
                run_length = 1;
            }
        }
        if (run_length >= 3) {
            run_lengths.push_back(run_length);
        }

        // Number of new characters needed.
        int num_new(0);
        if (!lower_case) {
            ++num_new;
        }
        if (!upper_case) {
            ++num_new;
        }
        if (!digit) {
            ++num_new;
        }
        
        // We can resolve some repeats if we need to insert or delete characters.
        int num_edits(0);
        if (s.size() < 6) {
            int num_inserts = 6 - s.size();
            // Some of the inserts can also satisfy num_new.
            num_new -= min(num_new, num_inserts);
            // Some of the inserts can break run lengths.
            for (int i = 0; i < run_lengths.size(); ++i) {
                int rl = run_lengths[i];
                while (num_inserts > 0 && rl >= 3) {
                    --num_inserts;
                    ++num_edits;
                    rl -= 2;
                }
                while (num_new > 0 && rl >= 3) {
                    --num_new;
                    ++num_edits;
                    rl -= 2;
                }
                run_lengths[i] = rl;
            }
            num_edits += num_inserts;
        } else if (s.size() > 20) {
            int num_deletes = s.size() - 20;
            // Some of the deletes can break run lengths at the same priority as substitutions.
            for (int i = 0; i < run_lengths.size(); ++i) {
                int rl = run_lengths[i];
                while (num_new > 0 && rl >= 3) {
                    --num_new;
                    ++num_edits;
                    rl -= 3;
                }
                if (rl >= 3 && num_deletes > 0 && rl % 3 == 0) {
                    --num_deletes;
                    ++num_edits;
                    rl -= 1;
                }
                run_lengths[i] = rl;
            }
            // Use the remainder of our deletion budget by priority.
            // This is given by number of deletes needed to break a repeat.
            for (int i = 0; i < run_lengths.size(); ++i) {
                int rl = run_lengths[i];
                if (rl >= 3 && num_deletes >= 2 && rl % 3 == 1) {
                    num_deletes -= 2;
                    num_edits += 2;
                    rl -= 2;
                }
                run_lengths[i] = rl;
            }
            for (int i = 0; i < run_lengths.size(); ++i) {
                int rl = run_lengths[i];
                while (rl >= 3 && num_deletes >= 3 && rl % 3 == 2) {
                    num_deletes -= 3;
                    num_edits += 3;
                    rl -= 3;
                }
                run_lengths[i] = rl;
            }
            num_edits += num_deletes;
        }
        
        // All remaining repeats will now be broken by substitutions.
        int num_replace(0);
        for (int rl : run_lengths) {
            num_replace += rl / 3;
        }
        num_edits += num_replace;
        
        // Some num_new can be satisfied by above substitutions.
        num_new -= min(num_new, num_replace);
        num_edits += num_new;

        return num_edits;
    }
};