22 Jun 2024•PHP•Hard

Strong Password Checker

find minimum steps to make password strong by handling length, character types, and repeating sequences.

handle three cases: too short, too long, just right. for each, count missing character types and repeating sequences. prioritize fixes that solve multiple issues.

for long passwords, use deletions to break repeating sequences efficiently. for short passwords, use insertions. for correct length, use replacements.

requirements

length 6-20
contains lowercase, uppercase, digit
no three consecutive same characters

complexity

O(n) time to scan password and count issues. O(1) space. greedy approach handles all cases.

Solution files

PHP•strong-password-checker/solution.php

class Solution {

function strongPasswordChecker($password) {
    $n = strlen($password);
    
    $hasLower = preg_match(class="syntax-string">'/[a-z]/', $password);
    $hasUpper = preg_match(class="syntax-string">'/[A-Z]/', $password);
    $hasDigit = preg_match(class="syntax-string">'/[class="syntax-number">0-class="syntax-number">9]/', $password);
    
    $missingTypes = class="syntax-number">3 - ($hasLower + $hasUpper + $hasDigit);
    
    $replacements = class="syntax-number">0;
    $oneMod = $twoMod = class="syntax-number">0;
    
    $i = class="syntax-number">2;
    while ($i < $n) {
        if ($password[$i] == $password[$i - class="syntax-number">1] && $password[$i - class="syntax-number">1] == $password[$i - class="syntax-number">2]) {
            $length = class="syntax-number">2;
            while ($i < $n && $password[$i] == $password[$i - class="syntax-number">1]) {
                $length++;
                $i++;
            }
            $replacements += intval($length / class="syntax-number">3);
            if ($length % class="syntax-number">3 == class="syntax-number">0) {
                $oneMod++;
            } elseif ($length % class="syntax-number">3 == class="syntax-number">1) {
                $twoMod++;
            }
        } else {
            $i++;
        }
    }
    
    if ($n < class="syntax-number">6) {
        return max($missingTypes, class="syntax-number">6 - $n);
    } elseif ($n <= class="syntax-number">20) {
        return max($missingTypes, $replacements);
    } else {
        $deletions = $n - class="syntax-number">20;
        
        $replacements -= min($deletions, $oneMod);
        $deletions -= min($deletions, $oneMod);
        
        $replacements -= min(intval($deletions / class="syntax-number">2), $twoMod);
        $deletions -= min(intval($deletions / class="syntax-number">2), $twoMod) * class="syntax-number">2;
        
        $replacements -= intval($deletions / class="syntax-number">3);
        
        return $n - class="syntax-number">20 + max($missingTypes, $replacements);
    }
}
}

$solution = new Solution();
echo $solution->strongPasswordChecker(class="syntax-string">"a") . class="syntax-string">"\n";
echo $solution->strongPasswordChecker(class="syntax-string">"aA1") . class="syntax-string">"\n";
echo $solution->strongPasswordChecker(class="syntax-string">"1337C0d3") . class="syntax-string">"\n";