Question

420. Strong Password Checker

中文文档

Description

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., "Baaabb0" is weak, but "Baaba0" is strong).

Given a string password, return _the minimum number of steps required to make password strong. if 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.

 

Example 1:

Input: password = "a"
Output: 5

Example 2:

Input: password = "aA1"
Output: 3

Example 3:

Input: password = "1337C0d3"
Output: 0

 

Constraints:

• 1 <= password.length <= 50
• password consists of letters, digits, dot '.' or exclamation mark '!'.

Solutions

Solution 1

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 {
  public int strongPasswordChecker(String password) {
    int types = countTypes(password);
    int n = password.length();
    if (n < 6) {
      return Math.max(6 - n, 3 - types);
    }
    char[] chars = password.toCharArray();
    if (n <= 20) {
      int replace = 0;
      int cnt = 0;
      char prev = '~';
      for (char curr : chars) {
        if (curr == prev) {
          ++cnt;
        } else {
          replace += cnt / 3;
          cnt = 1;
          prev = curr;
        }
      }
      replace += cnt / 3;
      return Math.max(replace, 3 - types);
    }
    int replace = 0, remove = n - 20;
    int remove2 = 0;
    int cnt = 0;
    char prev = '~';
    for (char curr : chars) {
      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 = Math.min(Math.min(replace, remove2), remove / 2);
    replace -= use2;
    remove -= use2 * 2;

    int use3 = Math.min(replace, remove / 3);
    replace -= use3;
    remove -= use3 * 3;
    return (n - 20) + Math.max(replace, 3 - types);
  }

  private int countTypes(String s) {
    int a = 0, b = 0, c = 0;
    for (char ch : s.toCharArray()) {
      if (Character.isLowerCase(ch)) {
        a = 1;
      } else if (Character.isUpperCase(ch)) {
        b = 1;
      } else if (Character.isDigit(ch)) {
        c = 1;
      }
    }
    return a + b + c;
  }
}

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