Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/420.html
420. Strong Password Checker
Level
Hard
Description
A password is considered strong if below conditions are all met:
- It has at least 6 characters and at most 20 characters.
- It must contain at least one lowercase letter, at least one uppercase letter, and at least one digit.
- It must NOT contain three repeating characters in a row (“…aaa…” is weak, but “…aa…a…” is strong, assuming other conditions are met). Write a function strongPasswordChecker(s), that takes a string s as input, and return the MINIMUM change required to make s a strong password. If s is already strong, return 0.
Insertion, deletion or replace of any one character are all considered as one change.
Solution
Use a priority queue to store the lengths of repeating characters, where the elements are sorted according to the results of modulo 3 in ascending order. Loop over s, check whether a lowercase letter, an uppercase letter and a digit exists, and find repeating characters and add the lengths into the priority queue. Then deal with the string under cases where length is less than 6 and length is greater than 20, respectively.
-
class Solution { public int strongPasswordChecker(String s) { int length = s.length(); if (length == 0) return 6; PriorityQueue<Integer> priorityQueue = new PriorityQueue<Integer>(new Comparator<Integer>() { public int compare(Integer num1, Integer num2) { return num1 % 3 - num2 % 3; } }); int repeatingCount = 1; int lowerCaseCount = 1, upperCaseCount = 1, digitCount = 1; char c0 = s.charAt(0); if (Character.isLowerCase(c0)) lowerCaseCount = 0; else if (Character.isUpperCase(c0)) upperCaseCount = 0; else if (Character.isDigit(c0)) digitCount = 0; char prevC = c0; for (int i = 1; i < length; i++) { char c = s.charAt(i); if (Character.isLowerCase(c)) lowerCaseCount = 0; else if (Character.isUpperCase(c)) upperCaseCount = 0; else if (Character.isDigit(c)) digitCount = 0; if (c == prevC) repeatingCount++; else { if (repeatingCount >= 3) priorityQueue.offer(repeatingCount); repeatingCount = 1; } prevC = c; } if (repeatingCount >= 3) priorityQueue.offer(repeatingCount); int typeCount = lowerCaseCount + upperCaseCount + digitCount; int changes = 0; if (length == 5) { if (typeCount >= 2 || repeatingCount == 5) return typeCount; else return 1; } else if (length < 5) return 6 - length; while (!priorityQueue.isEmpty() && length > 20) { int curRepeatingCount = priorityQueue.poll(); changes++; length--; curRepeatingCount--; if (curRepeatingCount >= 3) priorityQueue.offer(curRepeatingCount); } if (length > 20) changes += length - 20 + typeCount; else { int curCount = 0; while (!priorityQueue.isEmpty()) { int curRepeatingCount = priorityQueue.poll(); curCount += curRepeatingCount / 3; } changes += Math.max(curCount, typeCount); } return changes; } } -
class Solution: def strongPasswordChecker(self, password: str) -> int: def countTypes(s): a = b = c = 0 for ch in s: if ch.islower(): a = 1 elif ch.isupper(): b = 1 elif ch.isdigit(): c = 1 return a + b + c types = countTypes(password) n = len(password) if n < 6: return max(6 - n, 3 - types) if n <= 20: replace = cnt = 0 prev = '~' for curr in password: if curr == prev: cnt += 1 else: replace += cnt // 3 cnt = 1 prev = curr replace += cnt // 3 return max(replace, 3 - types) replace = cnt = 0 remove, remove2 = n - 20, 0 prev = '~' for curr in password: if curr == prev: cnt += 1 else: if remove > 0 and cnt >= 3: if cnt % 3 == 0: remove -= 1 replace -= 1 elif cnt % 3 == 1: remove2 += 1 replace += cnt // 3 cnt = 1 prev = curr if remove > 0 and cnt >= 3: if cnt % 3 == 0: remove -= 1 replace -= 1 elif cnt % 3 == 1: remove2 += 1 replace += cnt // 3 use2 = min(replace, remove2, remove // 2) replace -= use2 remove -= use2 * 2 use3 = min(replace, remove // 3) replace -= use3 remove -= use3 * 3 return n - 20 + max(replace, 3 - types) ############ class Solution(object): def strongPasswordChecker(self, s): """ :type s: str :rtype: int """ complexBal = 3 if any(c in string.lowercase for c in s): complexBal -= 1 if any(c in string.uppercase for c in s): complexBal -= 1 if any(c.isdigit() for c in s): complexBal -= 1 one = 0 two = 0 p = 2 replace = 0 while p < len(s): if s[p] == s[p - 1] == s[p - 2]: length = 2 while p < len(s) and s[p] == s[p - 1]: p += 1 length += 1 replace += length / 3 if length % 3 == 0: one += 1 if length % 3 == 1: two += 1 else: p += 1 if len(s) < 6: return max(complexBal, 6 - len(s)) elif len(s) <= 20: return max(complexBal, replace) else: redundant = len(s) - 20 replace -= min(redundant, one) replace -= min(max(redundant - one, 0), two * 2) / 2 replace -= max(redundant - one - two * 2, 0) / 3 return redundant + max(complexBal, replace) -
class Solution { public: int strongPasswordChecker(string password) { int types = countTypes(password); int n = password.size(); if (n < 6) return max(6 - n, 3 - types); if (n <= 20) { int replace = 0, cnt = 0; char prev = '~'; for (char& curr : password) { if (curr == prev) ++cnt; else { replace += cnt / 3; cnt = 1; prev = curr; } } replace += cnt / 3; return max(replace, 3 - types); } int replace = 0, remove = n - 20; int remove2 = 0; int cnt = 0; char prev = '~'; for (char& curr : password) { if (curr == prev) ++cnt; else { if (remove > 0 && cnt >= 3) { if (cnt % 3 == 0) { --remove; --replace; } else if (cnt % 3 == 1) ++remove2; } replace += cnt / 3; cnt = 1; prev = curr; } } if (remove > 0 && cnt >= 3) { if (cnt % 3 == 0) { --remove; --replace; } else if (cnt % 3 == 1) ++remove2; } replace += cnt / 3; int use2 = min(min(replace, remove2), remove / 2); replace -= use2; remove -= use2 * 2; int use3 = min(replace, remove / 3); replace -= use3; remove -= use3 * 3; return (n - 20) + max(replace, 3 - types); } int countTypes(string& s) { int a = 0, b = 0, c = 0; for (char& ch : s) { if (islower(ch)) a = 1; else if (isupper(ch)) b = 1; else if (isdigit(ch)) c = 1; } return a + b + c; } };