In this Leetcode Strong Password Checker problem solution A password is considered strong if the below conditions are all met:
- It has at least 6 characters and at most 20 characters.
- It contains at least one lowercase letter, at least one uppercase letter, and at least one digit.
- 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:
- Insert one character to password,
- Delete one character from password, or
- Replace one character of password with another character.
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; } };