LeetCode Problem 420

Difficulty: 🔴 Hard
Topics: String, Greedy, Heap (Priority Queue)

Solution

Strong Password Checker

Problem Understanding

The problem asks us to determine the minimum number of operations required to transform a given password into a "strong" password according to three rules.

A strong password must satisfy all of the following conditions:

1. The password length must be between 6 and 20 characters inclusive.
2. The password must contain at least one lowercase letter, at least one uppercase letter, and at least one digit.
3. The password must not contain three identical consecutive characters.

The input is a single string called password. The output is an integer representing the minimum number of edits needed to make the password valid.

Each edit operation can be one of three actions:

• Insert a character
• Delete a character
• Replace a character

The constraints are relatively small, the password length is at most 50, but the challenge is not brute computational scale. The difficulty comes from balancing multiple constraints simultaneously. A single operation can sometimes solve several problems at once. For example, replacing a repeated character with a digit might both break a repetition and satisfy the missing digit requirement.

Several edge cases make this problem tricky:

• Very short passwords where insertions are unavoidable
• Very long passwords where deletions are mandatory
• Passwords with many repeated sequences
• Passwords missing multiple character categories
• Cases where one operation can satisfy multiple requirements
• Long repeated sequences where careful deletion placement minimizes replacements

A naive implementation often fails because it treats each rule independently instead of optimizing globally.

Approaches

Brute Force Approach

A brute force solution would attempt all possible valid transformations using breadth first search or exhaustive recursion. At each step, it would try every possible insertion, deletion, and replacement, then check whether the resulting password is strong.

This approach is conceptually correct because it explores every reachable password configuration and finds the minimum number of edits.

However, it is computationally infeasible. At every position we could:

• Insert many possible characters
• Replace with many possible characters
• Delete characters

The branching factor becomes enormous very quickly. Even for passwords of moderate length, the state space explodes exponentially.

The brute force approach therefore cannot practically solve the problem within reasonable time limits.

Optimal Greedy Approach

The key insight is that the three constraints interact in predictable ways.

We can separately analyze:

• Missing character categories
• Repeating character runs
• Length violations

The most important observation is that repeated sequences determine replacement requirements. For any run of length L, we need L // 3 replacements if we only use replacements.

For example:

• "aaa" requires 1 replacement
• "aaaaaa" requires 2 replacements
• "aaaaaaaa" requires 2 replacements

When the password is too long, deletions become mandatory. The crucial optimization is that deletions can reduce the number of required replacements. We therefore greedily delete characters from repetition groups where deletions provide the greatest benefit.

The deletion strategy depends on the remainder modulo 3:

• Groups with length % 3 == 0 benefit immediately from one deletion
• Groups with length % 3 == 1 benefit from two deletions
• Groups with length % 3 == 2 benefit from three deletions

This greedy ordering minimizes the total operations.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	Exponential	Explores all possible edit sequences
Optimal	O(n)	O(n)	Greedy analysis of repetitions and length

Algorithm Walkthrough

1. Count missing character categories.

We scan the password once and determine whether it contains:

• A lowercase letter
• An uppercase letter
• A digit

The number of missing categories is important because replacements or insertions can simultaneously satisfy these requirements. 2. Identify repeating character groups.

We scan the string and locate contiguous runs of identical characters.

For example:

• "aaabbcccc" produces runs of lengths [3, 2, 4]

Any run with length at least 3 violates the repetition rule. 3. Handle the short password case.

If the password length is less than 6, insertions are required.

Insertions can also fix:

• Missing character types
• Repetition violations

Therefore, the answer becomes:

max(missing_types, 6 - length)

because each insertion can potentially address both issues simultaneously. 4. Compute replacement requirements for valid-length passwords.

For every repetition group of length L, the required replacements are:

$\left\lfloor \frac{L}{3} \right\rfloor$

We sum this value across all groups. 5. Handle the valid-length case.

If the password length is already between 6 and 20 inclusive, no deletions are needed.

The final answer is:

max(missing_types, replacements)

because replacements can simultaneously fix missing categories and repeated sequences. 6. Handle the overlength case.

If the password length exceeds 20, deletions are mandatory.

Let:

$\text{deletions} = n - 20$

We greedily apply deletions to repetition groups to reduce future replacement costs. 7. Prioritize deletions by modulo class.

For a repetition group of length L:

• If L % 3 == 0, deleting 1 character reduces replacements by 1
• If L % 3 == 1, deleting 2 characters reduces replacements by 1
• If L % 3 == 2, deleting 3 characters reduces replacements by 1

We process groups in this order because it gives the best reduction per deletion. 8. Apply remaining deletions.

After targeted deletions, any remaining deletions can still reduce replacements further in chunks of three. 9. Compute the final answer.

The total operations equal:

mandatory deletions + max(missing_types, remaining_replacements)

Why it works

The algorithm works because every constraint can be quantified independently, and each operation has predictable effects.

For short passwords, insertions dominate because length must increase. For valid-length passwords, replacements dominate because no deletions are required. For overly long passwords, deletions are unavoidable, so the optimal strategy is to use deletions where they maximally reduce future replacements.

The modulo-based greedy deletion ordering is optimal because it minimizes replacement reduction cost per deletion.

Python Solution

class Solution:
    def strongPasswordChecker(self, password: str) -> int:
        n = len(password)

        has_lower = any(c.islower() for c in password)
        has_upper = any(c.isupper() for c in password)
        has_digit = any(c.isdigit() for c in password)

        missing_types = 3 - has_lower - has_upper - has_digit

        groups = []
        i = 0

        while i < n:
            j = i
            while j < n and password[j] == password[i]:
                j += 1

            length = j - i
            if length >= 3:
                groups.append(length)

            i = j

        if n < 6:
            return max(missing_types, 6 - n)

        replacements = sum(length // 3 for length in groups)

        if n <= 20:
            return max(missing_types, replacements)

        deletions = n - 20
        remaining_deletions = deletions

        groups.sort(key=lambda length: length % 3)

        for idx in range(len(groups)):
            length = groups[idx]

            if remaining_deletions <= 0:
                break

            if length % 3 == 0:
                delete_needed = 1
            elif length % 3 == 1:
                delete_needed = 2
            else:
                delete_needed = 3

            if remaining_deletions >= delete_needed:
                groups[idx] -= delete_needed
                remaining_deletions -= delete_needed
                replacements -= 1

        for idx in range(len(groups)):
            if remaining_deletions <= 0:
                break

            length = groups[idx]

            if length < 3:
                continue

            extra_reduce = min(
                replacements,
                remaining_deletions // 3
            )

            reduction = min(
                extra_reduce,
                (groups[idx] - 2) // 3
            )

            groups[idx] -= reduction * 3
            remaining_deletions -= reduction * 3
            replacements -= reduction

        return deletions + max(missing_types, replacements)

The implementation begins by checking which character categories are present. The missing_types variable records how many required categories are absent.

Next, the code scans the password and records all repetition groups with length at least 3. These groups are the only ones relevant for replacement calculations.

If the password is too short, the algorithm immediately returns max(missing_types, 6 - n) because insertions can solve both problems simultaneously.

If the length is already valid, the only remaining concern is balancing missing categories against repetition fixes. Replacements can address both issues at once, so the maximum of the two determines the answer.

For overly long passwords, deletions become mandatory. The algorithm sorts repetition groups by length % 3 because this determines deletion efficiency. It greedily applies deletions where they most effectively reduce replacements.

Finally, after all deletions are processed, the answer combines mandatory deletions with the remaining replacement or missing-category requirements.

Go Solution

package main

import (
	"sort"
	"unicode"
)

func strongPasswordChecker(password string) int {
	n := len(password)

	hasLower := false
	hasUpper := false
	hasDigit := false

	for _, ch := range password {
		if unicode.IsLower(ch) {
			hasLower = true
		}
		if unicode.IsUpper(ch) {
			hasUpper = true
		}
		if unicode.IsDigit(ch) {
			hasDigit = true
		}
	}

	missingTypes := 0
	if !hasLower {
		missingTypes++
	}
	if !hasUpper {
		missingTypes++
	}
	if !hasDigit {
		missingTypes++
	}

	groups := []int{}

	for i := 0; i < n; {
		j := i

		for j < n && password[j] == password[i] {
			j++
		}

		length := j - i

		if length >= 3 {
			groups = append(groups, length)
		}

		i = j
	}

	if n < 6 {
		return max(missingTypes, 6-n)
	}

	replacements := 0
	for _, length := range groups {
		replacements += length / 3
	}

	if n <= 20 {
		return max(missingTypes, replacements)
	}

	deletions := n - 20
	remainingDeletions := deletions

	sort.Slice(groups, func(i, j int) bool {
		return groups[i]%3 < groups[j]%3
	})

	for i := 0; i < len(groups); i++ {
		if remainingDeletions <= 0 {
			break
		}

		deleteNeeded := 0

		if groups[i]%3 == 0 {
			deleteNeeded = 1
		} else if groups[i]%3 == 1 {
			deleteNeeded = 2
		} else {
			deleteNeeded = 3
		}

		if remainingDeletions >= deleteNeeded {
			groups[i] -= deleteNeeded
			remainingDeletions -= deleteNeeded
			replacements--
		}
	}

	for i := 0; i < len(groups); i++ {
		if remainingDeletions <= 0 {
			break
		}

		if groups[i] < 3 {
			continue
		}

		reduction := min(
			(groups[i]-2)/3,
			remainingDeletions/3,
		)

		groups[i] -= reduction * 3
		remainingDeletions -= reduction * 3
		replacements -= reduction
	}

	return deletions + max(missingTypes, replacements)
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

The Go implementation follows the same algorithmic structure as the Python version. The main differences are related to language mechanics.

Go does not provide Python-style generator expressions, so category checks are implemented using explicit loops and boolean flags.

The repetition groups are stored in a slice of integers. Sorting is performed using sort.Slice.

Go strings are byte indexed, which is safe here because the problem constraints limit input to ASCII characters.

No special nil handling is needed because empty slices behave naturally in loops and sorting operations.

Worked Examples

Example 1

Input:

password = "a"

Initial analysis:

Property	Value
Length	1
Has lowercase	Yes
Has uppercase	No
Has digit	No
Missing types	2

There are no repetition groups.

The password is too short:

Requirement	Needed
Minimum length increase	5
Missing character types	2

Result:

max(5, 2) = 5

Answer:

5

Example 2

Input:

password = "aA1"

Initial analysis:

Property	Value
Length	3
Has lowercase	Yes
Has uppercase	Yes
Has digit	Yes
Missing types	0

No repetition groups exist.

The password is too short:

Requirement	Needed
Minimum length increase	3
Missing character types	0

Result:

max(3, 0) = 3

Answer:

3

Example 3

Input:

password = "1337C0d3"

Initial analysis:

Property	Value
Length	8
Has lowercase	Yes
Has uppercase	Yes
Has digit	Yes
Missing types	0

No repetition groups of length at least 3 exist.

The password already satisfies all rules.

Answer:

0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Single scans plus sorting bounded by password length
Space	O(n)	Stores repetition group lengths

The algorithm performs several linear scans over the password. The repetition group list contains at most n elements, so sorting remains bounded by the small input size. Since n <= 50, the implementation is extremely efficient in practice.

Test Cases

sol = Solution()

assert sol.strongPasswordChecker("a") == 5  # single lowercase, too short
assert sol.strongPasswordChecker("aA1") == 3  # valid categories, too short
assert sol.strongPasswordChecker("1337C0d3") == 0  # already strong

assert sol.strongPasswordChecker("aaa111") == 2  # repeated groups
assert sol.strongPasswordChecker("AAAAAA") == 2  # missing lowercase and digit
assert sol.strongPasswordChecker("aaaaaa") == 2  # missing uppercase and digit

assert sol.strongPasswordChecker("aaaaaaaaaaaaaaaaaaaaa") == 7  # over length with repeats
assert sol.strongPasswordChecker("ABABABABABABABABABAB1") == 2  # over length without repeats
assert sol.strongPasswordChecker("1111111111") == 3  # repeated digits

assert sol.strongPasswordChecker("Aa1Aa1") == 0  # exactly valid
assert sol.strongPasswordChecker("Aa1aaa") == 1  # one repetition violation
assert sol.strongPasswordChecker("Aa1bbbccc") == 2  # multiple repetition groups

assert sol.strongPasswordChecker("...") == 3  # invalid characters repeated
assert sol.strongPasswordChecker("aA1111") == 1  # single replacement fixes repetition
assert sol.strongPasswordChecker("aaaaaaaaaaAAAAAA123456") == 5  # long mixed case

assert sol.strongPasswordChecker("Aa1") == 3  # minimal valid categories but short
assert sol.strongPasswordChecker("Aa1Aa1Aa1Aa1Aa1Aa1") == 0  # exactly length 18 and valid
assert sol.strongPasswordChecker("aaaAAA111") == 3  # three separate repeating groups

Test	Why
"a"	Minimum length edge case
"aA1"	All categories present but too short
"1337C0d3"	Already valid password
"aaa111"	Multiple repetition groups
"AAAAAA"	Missing lowercase and digit
"aaaaaaaaaaaaaaaaaaaaa"	Overlength with large repetition
"ABABABABABABABABABAB1"	Overlength without repeats
"1111111111"	Repeated digit sequence
"Aa1Aa1"	Exact valid boundary
"Aa1bbbccc"	Multiple independent violations
"..."	Special character repetition
"aaaAAA111"	Several repetition groups together

Edge Cases

Extremely Short Passwords

A password like "a" is challenging because it violates multiple constraints simultaneously. It is too short and missing character categories. A naive solution might incorrectly add operations separately for each issue.

The implementation correctly recognizes that insertions can solve both problems simultaneously. Each inserted character can both increase length and introduce a missing category.

Very Long Repetitive Passwords

A password such as "aaaaaaaaaaaaaaaaaaaaa" exceeds the maximum length and contains a massive repetition group. A naive approach might first compute replacements and then add deletions independently, producing a nonminimal answer.

The implementation instead uses deletions strategically to reduce replacement requirements before calculating the final answer.

Multiple Independent Repetition Groups

Passwords like "aaaBBB111" contain several distinct violating runs. Each group independently contributes replacement requirements.

The implementation scans the password into separate repetition groups and computes their replacement costs independently, ensuring no violating sequence is missed or double counted.