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:

1. It has at least 6 characters and at most 20 characters.
2. It must contain at least one lowercase letter, at least one uppercase letter, and at least one digit.
3. 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.

• Java
• C++
• Python

• 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;
      }
  }
  

• Todo
  

• 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)
  
  

All Problems

All Solutions