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: Greedy

• Time complexity: O(n)
• Space complexity: O(1)

 

JavaScript

/**
 * @param {string} password
 * @return {number}
 */
const strongPasswordChecker = function (password) {
  const n = password.length;
  let lowercase = (uppercase = digit = 1);
  let replaces = (remainZero = remainOne = 0);

  for (let index = 0; index < n; index++) {
    const char = password[index];
    let repeat = 1;

    if (/\d/.test(char)) digit = 0;
    else if (/[a-z]/.test(char)) lowercase = 0;
    else if (/[A-Z]/.test(char)) uppercase = 0;

    while (index < n && password[index] === password[index + repeat]) {
      repeat += 1;
    }
    index += repeat - 1;
    if (repeat < 3) continue;
    const remain = repeat % 3;

    replaces += Math.floor(repeat / 3);
    if (remain === 0) remainZero += 1;
    if (remain === 1) remainOne += 1;
  }
  const missing = lowercase + uppercase + digit;

  if (n < 6) return Math.max(6 - n, missing);
  if (n <= 20) return Math.max(replaces, missing);
  const deletes = n - 20;

  // aaa => aa, 1 delete step replace 1 replace step
  replaces -= Math.min(deletes, remainZero);
  // aaaa => aa, 2 delete step replace 1 replace step
  replaces -= Math.floor(Math.min(Math.max(deletes - remainZero, 0), remainOne * 2) / 2);
  // aaaaa => aa, 3 delete step replace 1 replace step
  replaces -= Math.floor(Math.max(deletes - remainZero - remainOne * 2, 0) / 3);
  return deletes + Math.max(replaces, missing);
};