Introduction

In this blog post, we will explore how to solve the LeetCode problem "420" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

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 '!'.

Explanation

Here's a breakdown of the approach, followed by the Python code:

• Analyze Weaknesses: Identify the specific weaknesses in the password. This includes length violations, missing character types (lowercase, uppercase, digit), and repeating character sequences.
• Prioritize Length Correction: If the length is outside the allowed range, focus on correcting this first, as insertions/deletions affect the character positions and can influence the repeating character checks.

• Address Repeating Characters and Missing Types: While fixing the length, simultaneously try to cover missing character types and remove repeating characters optimally.

• Runtime Complexity: O(n), where n is the length of the password.

• Storage Complexity: O(1)

Code

    def strongPasswordChecker(password: str) -> int:
    n = len(password)
    missing = 0
    if not any('a' <= c <= 'z' for c in password):
        missing += 1
    if not any('A' <= c <= 'Z' for c in password):
        missing += 1
    if not any('0' <= c <= '9' for c in password):
        missing += 1

    repeats = []
    i = 0
    while i < n:
        j = i
        while j < n and password[i] == password[j]:
            j += 1
        length = j - i
        if length >= 3:
            repeats.append(length)
        i = j

    moves = 0
    if n < 6:
        moves += max(missing, 6 - n)
    elif n > 20:
        over = n - 20
        moves += over

        repeats.sort()  # Sort repeats to prioritize shorter ones
        for k in range(1, 3):
            i = 0
            while over > 0 and i < len(repeats):
                if repeats[i] < 3:
                    i += 1
                    continue

                reduction = min(over, (repeats[i] - 2) // k)
                repeats[i] -= reduction * k
                over -= reduction
                moves += reduction
                i += 1

        #Remaining deletions
        for i in range(len(repeats)):
            moves += (repeats[i]-2)
    else:
        for repeat in repeats:
            moves += (repeat - 2) // 3

    moves = max(moves, missing)
    return moves