0655HardStringGreedyHeap (Priority Queue)

Strengthening a Vault Code

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A vault keypad accepts a code as sound only when all four of these hold:

it is at least 6 and at most 20 characters long;
it contains at least one lowercase letter;
it contains at least one uppercase letter;
it contains at least one digit;
no character appears three or more times in a row.

In one step an engineer may insert one character anywhere in the code, delete one character from anywhere in it, or overwrite one character with a different one. Inserted and overwritten characters may be any lowercase letter, uppercase letter, digit, dot or exclamation mark.

Given the current code, return the smallest number of steps that leaves it sound. A code that is already sound needs none.

Examples

Example 1

Input: code = "Kp7"
Output: 3

The code already carries a lowercase letter, an uppercase letter and a digit, and no character repeats, so only its length falls short. Inserting three characters, for instance to reach "Kp7wz4", leaves a sound code.

Example 2

Input: code = "aaaB12"
Output: 1

The length is allowed and all three kinds are present, but the opening three characters are the same. Overwriting the middle one, for instance to reach "axaB12", leaves a sound code.

Example 3

Input: code = "......"
Output: 3

The length is allowed, but the code has no lowercase letter, no uppercase letter and no digit, and it carries runs of the same character. Overwriting the second, fourth and sixth characters, for instance to reach ".w.Q.5", leaves a sound code.

Constraints

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

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def steps_to_strengthen(code: str) -> int:

Java

public int stepsToStrengthen(String code)

The intended approach

Time O(n) for a code of n characters: one pass to find the runs, then a bounded sweep over them.Space O(n) for the run lengths.

Count how many of the three required kinds are absent, and split the code into runs of one repeated character. A run of length r needs r // 3 overwrites on its own. Below the minimum length, every step must be an insertion and an insertion can also supply a missing kind, so the answer is whichever of the two shortfalls is larger. Within the allowed length no insertion or deletion helps, so it is the larger of the missing kinds and the overwrite total, since one overwrite can do both jobs at once. Above the maximum length the surplus must be deleted, and a deletion placed inside a run can also cut that run's overwrite count: one deletion does it when the run length is a multiple of three, two when it is one more than a multiple, three otherwise, so deletions are spent in that order of value before the remaining overwrites and missing kinds are overlapped.

Pythonentry point: steps_to_strengthen

def steps_to_strengthen(code):
    size = len(code)
    lacking = 3
    if any(ch.islower() for ch in code):
        lacking -= 1
    if any(ch.isupper() for ch in code):
        lacking -= 1
    if any(ch.isdigit() for ch in code):
        lacking -= 1

    runs = []
    i = 0
    while i < size:
        j = i
        while j < size and code[j] == code[i]:
            j += 1
        runs.append(j - i)
        i = j

    if size < 6:
        # each insertion adds length and can supply a lacking kind at the same time
        return max(lacking, 6 - size)
    if size <= 20:
        return max(lacking, sum(r // 3 for r in runs))

    trims = size - 20
    left = trims
    # a run of length r needs r // 3 rewrites; trimming it can cut that count.
    # a run with r % 3 == 0 saves a rewrite for 1 trim, r % 3 == 1 for 2 trims,
    # and any other run for 3, so spend trims in that order of value.
    for rest in (0, 1, 2):
        cost = rest + 1
        for idx in range(len(runs)):
            while runs[idx] >= 3 and runs[idx] % 3 == rest and left >= cost:
                runs[idx] -= cost
                left -= cost
    return trims + max(lacking, sum(r // 3 for r in runs))

The obvious version

Breadth-first search over codes, where one move is a single insertion, deletion or overwrite, stopping the moment a sound code is reached. Explores an enormous number of codes and is only usable on short inputs, but it assumes nothing about runs or counting and so is an independent check on the whole rule set.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def _is_strong(code):
    if not 6 <= len(code) <= 20:
        return False
    if not any(ch.islower() for ch in code):
        return False
    if not any(ch.isupper() for ch in code):
        return False
    if not any(ch.isdigit() for ch in code):
        return False
    for i in range(len(code) - 2):
        if code[i] == code[i + 1] == code[i + 2]:
            return False
    return True


def bf_steps_to_strengthen(code):
    """Breadth-first over single edits. Independent of any counting argument."""
    if _is_strong(code):
        return 0
    pool = "abAB78"
    seen = {code}
    frontier = [code]
    steps = 0
    while frontier:
        steps += 1
        nxt = []
        for cur in frontier:
            n = len(cur)
            moves = []
            if n > 6:
                for i in range(n):
                    moves.append(cur[:i] + cur[i + 1:])
            if n < 20:
                for i in range(n + 1):
                    for ch in pool:
                        moves.append(cur[:i] + ch + cur[i:])
            for i in range(n):
                for ch in pool:
                    if ch != cur[i]:
                        moves.append(cur[:i] + ch + cur[i + 1:])
            for cand in moves:
                if cand in seen:
                    continue
                if _is_strong(cand):
                    return steps
                seen.add(cand)
                nxt.append(cand)
        frontier = nxt
    return -1

How this problem was checked

Reference solution executed against 18 test cases — 18 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in