Task 1: Strong Password
You are given a string, $str.
Write a script to find the minimum number of steps required to make $str a strong password. A password is strong if:
- It has at least 6 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 (e.g., "aaa" is invalid, but "aab" or "aba" is fine).
Method Explanation
The problem requires calculating the minimal number of insertions, deletions, or substitutions to fulfill all password criteria.
We analyze three conditions:
- Missing character categories: We check whether at least one lowercase letter, uppercase letter, and digit are present. If any are missing, we count each missing type.
- Consecutive repeats of length $\ge 3$: Whenever a sequence of $k$ identical consecutive characters appears, each sequence requires $\lfloor k / 3 \rfloor$ replacements to break the repeats (e.g., "aaaaa" length 5 requires $5 // 3 = 1$ change).
- Length constraints:
- If the string length $n \ge 6$, we can satisfy missing types and broken repeats simultaneously by choosing the replacing characters wisely. Thus, the answer is $\max(\text{missing\_types}, \text{repeats\_to\_fix})$.
- If $n < 6$, we need at least $6 - n$ insertions. An inserted character can break a repeating triplet or introduce a missing character class. The total steps required is $\max(\text{missing\_types} + \text{repeats\_to\_fix}, 6 - n)$.
Perl Solution
use v5.38;
use warnings;
use Type::Params -sigs;
use Types::Standard qw(Str);
signature_for strong_password_steps => (
method => 0,
positional => [ Str ],
);
sub strong_password_steps ($s) {
my $missing_types = 3;
$missing_types-- if $s =~ /[a-z]/;
$missing_types-- if $s =~ /[A-Z]/;
$missing_types-- if $s =~ /\d/;
my $repeats_to_fix = 0;
my $i = 2;
my $n = length($s);
while ( $i < $n ) {
if ( substr( $s, $i, 1 ) eq substr( $s, $i - 1, 1 ) && substr( $s, $i - 1, 1 ) eq substr( $s, $i - 2, 1 ) ) {
my $repeat_len = 3;
while ( $i + 1 < $n && substr( $s, $i + 1, 1 ) eq substr( $s, $i, 1 ) ) {
$repeat_len++;
$i++;
}
$repeats_to_fix += int( $repeat_len / 3 );
}
$i++;
}
my $total_steps;
if ( $n >= 6 ) {
$total_steps = ( $missing_types > $repeats_to_fix ) ? $missing_types : $repeats_to_fix;
}
else {
my $insertions_needed = 6 - $n;
my $sum = $missing_types + $repeats_to_fix;
$total_steps = ( $sum > $insertions_needed ) ? $sum : $insertions_needed;
}
return $total_steps;
}
Python Solution
import re
def strong_password_steps(s: str) -> int:
"""Calculate the minimum steps to make the password strong."""
missing_types = 3
if re.search(r"[a-z]", s):
missing_types -= 1
if re.search(r"[A-Z]", s):
missing_types -= 1
if re.search(r"\d", s):
missing_types -= 1
repeats_to_fix = 0
i = 2
n = len(s)
while i < n:
if s[i] == s[i - 1] == s[i - 2]:
repeat_len = 3
while i + 1 < n and s[i + 1] == s[i]:
repeat_len += 1
i += 1
repeats_to_fix += repeat_len // 3
i += 1
if n >= 6:
total_steps = max(missing_types, repeats_to_fix)
else:
total_steps = max(missing_types + repeats_to_fix, 6 - n)
return total_steps